3 ms·

Isn't every algorithm reversible if you save the inputs? If you have some algorithm A that turns an input bitstring N into an output bitstring M in K steps goi

Isn't every algorithm reversible if you save the inputs? If you have some algorithm A that turns an input bitstring N into an output bitstring M in K steps going through states S(0) ... S(K), then: 1. None of the states can repeat or you have an infinite loop. 2. For some step 0 < K0 < K, (A, N, K0) uniquely determines both S(K0-1) and S(K0+1): Run A on input N for K0+1 steps and record { S(K0-1), S(K0), S(K0+1) }. 3. So all computations are reversible given (A, N, K). Maybe physics wants something like "local reversibility"(a reverse-step must execute within fixed time), whereas CS works with "mathematical reversibility"(is it a computable one-to-one function?). The construction above doesn't execute within fixed time, but I don't think that's the correct fix: There are lots of dumb things I can do in constant-time. So why does Physics not allow me to write off all my electricity expenses, as long as I keep the data on backup tapes in a closet in case I get audited for reversibility?

einpoklum 6y ago
> Isn't every algorithm reversible if you save the inputs? 1. No, it might be probabilistic or non-deterministic. 2. Depends on your definition of reversibility. Maybe it's the ability to reverse a single, highly-localized, operation, such as an ALU operation; in which it doesn't help that you can repeat the computation all the way from the input to the previous state.
- nfoz 6y ago
  A pure turing machine doesn't have access to a real random number generator. So whatever your entropy source is, I think you need to consider that as one of your inputs.
wizzwizz4 6y ago
It actually does let you do that. Trouble is, unless you can reverse your backup tapes to their original state, that won't help you.
gnramires 6y ago
Operational reversibility of data would be a necessary but not sufficient condition for 0-energy (isoentropic) computation. Isoentropic (i.e. one that doesn't increase entropy) process needs, as you cite, microscopic reversibility ("local reversibility"), all the physical states of the machine itself must be reversible during the entire operation (i.e. each atom can only change state isoentropically); it's really a physical property of the computer and not a mathematical property of the computation. As I see it, this can only be achieved near 0K under very special conditions, essentially like a quantum computer (QCs also operate under this reversible regime, but not in the interest of energy saving).

einpoklum 6y ago

> Isn't every algorithm reversible if you save the inputs? 1. No, it might be probabilistic or non-deterministic. 2. Depends on your definition of reversibility. Maybe it's the ability to reverse a single, highly-localized, operation, such as an ALU operation; in which it doesn't help that you can repeat the computation all the way from the input to the previous state.

nfoz 6y ago
A pure turing machine doesn't have access to a real random number generator. So whatever your entropy source is, I think you need to consider that as one of your inputs.

wizzwizz4 6y ago

It actually does let you do that. Trouble is, unless you can reverse your backup tapes to their original state, that won't help you.

gnramires 6y ago

Operational reversibility of data would be a necessary but not sufficient condition for 0-energy (isoentropic) computation. Isoentropic (i.e. one that doesn't increase entropy) process needs, as you cite, microscopic reversibility ("local reversibility"), all the physical states of the machine itself must be reversible during the entire operation (i.e. each atom can only change state isoentropically); it's really a physical property of the computer and not a mathematical property of the computation. As I see it, this can only be achieved near 0K under very special conditions, essentially like a quantum computer (QCs also operate under this reversible regime, but not in the interest of energy saving).