Hacker News Reader

Comment by mathgradthrow | Hacker News Reader

A big problem with the idea of physical reversible computing is the assumption that you get to start with a blank tape. Blank tapes are trivial to acquire if I can erase bits, but if I start with a tape in some state, creating working space in memory reverisbly is equivalent (identical) to lossless compression, which is not generally achievable.

If you start with blank tape then it isn't really reversible computing, you're just doing erasure up front.

View on HN

Yes, but erasing the tape once is much better than erasing the tape many times over.

I don't think your criticism is applicable to any reversible-computing schemes that I've seen proposed, including this one. They don't assume that you get to start with a blank memory (tapelike or otherwise); rather, they propose approaches to constructing a memory device in a known state, out of atoms.

What do you think you're saying here? Building a memory device in a known configuration is erasing bits.

Yes, building a memory device in a known configuration is erasing bits. Once you've built it, you can use it until it breaks. As long as you decompute the bits you've temporarily stored in it, restoring it to its original configuration, you don't inherently have to dissipate any energy to use it. You can reuse it an arbitrarily large number of times after building it once. If you want to compute some kind of final result that you store, rather than decomputing it, that does cost you energy in the long run, but that energy can be arbitrarily small compared to the computation that was required to reach it.

Consider the case, for example, of cracking an encryption key; each time you try an incorrect key, you reverse the whole computation. It's only when you hit on the right key that you store a 1 bit indicating success and a copy of the cracked key; then you reverse the last encryption attempt, leaving only the key. Maybe you've done 2¹²⁸ trial encryptions, each requiring 2¹³ bit operations, for a total of 2¹⁴¹ bit operations of reversible computation, but you only need to store 2⁷ bits to get the benefit, a savings of 2¹³⁵×.

Most practical computations don't enjoy quite such a staggering reduction in thermodynamic entropy from reversible computation, but a few orders of magnitude is commonplace.

It sounds like you could benefit from reading an introduction to the field. Though I may be biased, I can recommend Michael Frank's introduction from 20 years ago: https://web1.eng.famu.fsu.edu/~mpf/ip1-Frank.pdf

Thanks for the shout-out, Kragen!

A more complete resource for finding my work count be found at https://revcomp.info.

What would you recommend newcomers read as an introduction to the field today? Would it be one of your own papers, or has someone else written an overview you'd recommend?

I didn't realize you'd left Sandia! I hope everything is going well.

Reply on news.ycombinator.com