News for hackers. Stuff that matters.
Re:Building a Completely Reversible Computer by openasocket on Wednesday April 19, 2017 @04:19PM (#14151390)
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.
Re:Building a Completely Reversible Computer by SilasX on Wednesday April 19, 2017 @05:30PM (#14151973)
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.

Re:Building a Completely Reversible Computer by aparent on Wednesday April 19, 2017 @06:08PM (#14152270)
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.