Comment by MichaelBurge | Hacker News Reader

Comment by MichaelBurge | Hacker News Reader

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?

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).

> 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.

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.

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.

Reply on news.ycombinator.com