4 ms·

As far as I understand it, you can construct reversible functions this way, but many interesting functions are irreversible (for example an OCR process generate

by jhgb 5y ago

As far as I understand it, you can construct reversible functions this way, but many interesting functions are irreversible (for example an OCR process generates an ASCII string, but you can't reverse the process to get the original bitmap from the ASCII string).

ajb 5y ago
A reversible function can do all the work of any given irreversible function. Specifically, supposed your reversible function is G(x). a reversible function for this is then (X, Y) => (X, G(X) ^ Y)
- jhgb 5y ago
  And how do you get G(X) from (X, G(X) ^ Y), then? (I assume you meant "your irreversible function is G(x)"?) That sounds like "you can find a reversible component in an irreversible calculation", which is probably true, but maybe practically meaningless: You were yourself talking about "an exponential increase in space", but if I understood this Landauer limit thingy correctly, this also gives you an exponential limit in power dissipated.
  - tromp 5y ago
    You get G(X) by feeding in Y=0. And yes, they meant irreversible function G.
    - jhgb 5y ago
      That sounds to me like you're trying to cheat physics here. If there's a physical limit to calculating an irreversible G(X), I don't see how you magically remove it by pretending that something including G(X) is reversible and then by ignoring what you've just added.
      - ajb 5y ago
        What I'm trying to address is the claim that there is something 'interesting' about irreversible functions that you can't do using reversible functions. Irreversible functions just discard information in the course of calculating some value. You can simply save the discarded information and have the same calculated value in your result, and have a reversible function. Nothing about this violates physics. Obviously it's not exactly the same function - it has more outputs and inputs. But it can be used as a subcomponent of any operation where you needed the reversible function. there is no such thing as a class of 'interesting' functions which cannot be used in this way.
        jhgb 5y ago
        What is the size of the "nondiscarded information" you must save in this case?
  - jlokier 5y ago
    A subtle factor is that for most interesting computations, the size of input and output you are interested in is much smaller than the size of temporary states required by the computation to produce that output. It is useful to distinguish between the "middle" of a computation and "output stage". Using irreversible computation, the middle requires a potentially large state, and a correspondingly large energy consumption. You can often transform an irreversible computation to a reversible "middle", with an encoded result such that the "output stage" has to do projection and decoding, with that final step consuming energy, but not as much energy as the original irreversible computation would consume. You do the computation while preserving every bit of information needed to run the whole computation backwards, then read just the output bits you want in the result, then run the middle computation backwards. It's like compressing a spring and then accepting the energy back from the spring: That doesn't consume much energy, it just stores it and gives it back. A reversible computation is a very complicated spring, and you read the the output before letting it give back the energy from the reversible part. As you can chain computations with "output" only at the end of the chain, it's useful to think of reversible, and maybe linear (e.g. one-shot encoded) computations as building blocks. So I think Gravyness's question is a good, curious question, and there is something to it. Even though you can't build a complete, standard computer that way. There are many practical and scaling obstacles. It has a lot in common with quantum computation (the ideal, theoretical version), though they are not the same thing. An (ideal, theoretical) quantum computation is linear and reversible, but on quantum states instead of classical states, and there is an energy-consuming input and output stage.

by jhgb 5y ago

ajb 5y ago

A reversible function can do all the work of any given irreversible function. Specifically, supposed your reversible function is G(x). a reversible function for this is then (X, Y) => (X, G(X) ^ Y)

jhgb 5y ago
And how do you get G(X) from (X, G(X) ^ Y), then? (I assume you meant "your irreversible function is G(x)"?) That sounds like "you can find a reversible component in an irreversible calculation", which is probably true, but maybe practically meaningless: You were yourself talking about "an exponential increase in space", but if I understood this Landauer limit thingy correctly, this also gives you an exponential limit in power dissipated.
- tromp 5y ago
  You get G(X) by feeding in Y=0. And yes, they meant irreversible function G.
  - jhgb 5y ago
    That sounds to me like you're trying to cheat physics here. If there's a physical limit to calculating an irreversible G(X), I don't see how you magically remove it by pretending that something including G(X) is reversible and then by ignoring what you've just added.
    - ajb 5y ago
      What I'm trying to address is the claim that there is something 'interesting' about irreversible functions that you can't do using reversible functions. Irreversible functions just discard information in the course of calculating some value. You can simply save the discarded information and have the same calculated value in your result, and have a reversible function. Nothing about this violates physics. Obviously it's not exactly the same function - it has more outputs and inputs. But it can be used as a subcomponent of any operation where you needed the reversible function. there is no such thing as a class of 'interesting' functions which cannot be used in this way.
      - jhgb 5y ago
        What is the size of the "nondiscarded information" you must save in this case?
- jlokier 5y ago
  A subtle factor is that for most interesting computations, the size of input and output you are interested in is much smaller than the size of temporary states required by the computation to produce that output. It is useful to distinguish between the "middle" of a computation and "output stage". Using irreversible computation, the middle requires a potentially large state, and a correspondingly large energy consumption. You can often transform an irreversible computation to a reversible "middle", with an encoded result such that the "output stage" has to do projection and decoding, with that final step consuming energy, but not as much energy as the original irreversible computation would consume. You do the computation while preserving every bit of information needed to run the whole computation backwards, then read just the output bits you want in the result, then run the middle computation backwards. It's like compressing a spring and then accepting the energy back from the spring: That doesn't consume much energy, it just stores it and gives it back. A reversible computation is a very complicated spring, and you read the the output before letting it give back the energy from the reversible part. As you can chain computations with "output" only at the end of the chain, it's useful to think of reversible, and maybe linear (e.g. one-shot encoded) computations as building blocks. So I think Gravyness's question is a good, curious question, and there is something to it. Even though you can't build a complete, standard computer that way. There are many practical and scaling obstacles. It has a lot in common with quantum computation (the ideal, theoretical version), though they are not the same thing. An (ideal, theoretical) quantum computation is linear and reversible, but on quantum states instead of classical states, and there is an energy-consuming input and output stage.