Hacker News Reader

What are the limitations to a completely reversible computer? I'm guessing it's still Turing complete, but do you pay a cost in terms of asymptotic complexity? I'm guessing you can make a program reversible trivially by doing something like making everything immutable and only ever appending new data, but of course that's extremely inefficient in terms of memory. Of course, I might be missing the core concept here.

View on HN

AIUI, it's just a linear penalty because, at worst, you have to run each computation backwards to "uncompute it".

That's under the (necessary) assumption that you don't even try to avoid erasure operations that need for their own sake rather than as an intermediate step.

It is a bit more complicated then that. The only penalty to time is a constant factor if you are willing to use space proportional to the computation time. I did a bit of work on how to do time-space trade-offs in reversible circuits in my masters thesis http://hdl.handle.net/10012/10949.

Reply on news.ycombinator.com