For those who want to look into this in more depth, Conservative Logic by Fredkin and Toffoli [1] is a foundational paper exploring in detail how the principle of reversible computing impacts the underlying logic used for computation down to the logic gates. It is very readable.
[Edit: the video recommended by gbrown_ elsewhere in this thread (https://news.ycombinator.com/item?id=26295043) refers to this paper and also shows how it is possible to move beyond the constraints introduced in it.]
Waaay back in uni I was taught that eventually computing will have to go reversible because of the mentioned “von Neumann–Landauer limit”. So, your program will run each instruction forward, then again as the stack rewinds (instead of stack pops). But, this 2X penalty will enable a >2X clock rate increase due to lower thermals.
Rewinding code also has the side effect of automatic garbage collection. The challenge becomes copying out end results before rewinding without re-introducing thermal waste.
In the meantime chips are utilizing partial measures against it like sending excess bits to recycling pools. So, A|B results in 2 bits in, 1 bit out as a useful result and 1 bit shuttled off for recycling.
Backing this up, I recently learned that quantum computer programs must be reversible if they are to function.
The way I understand it is that you don't necessarily actually have to rewind anything, just that destroying information is what causes the extra energy need and is therefore not allowed.
The principle is already in use in areas like differential signalling, where a single bit is transmitted on 2 lines at the same time: 0 as (0,1), 1 as (1,0), so that the total charge in the circuit never changes. In simple signalling like SPI, there is only one line, and the system has a different charge depending on the transmitted value, so the charge has to be fed into and removed from the system all the time.
As for quantum computing, reversibility is coming as a direct consequence of the inability to either destroy or copy quantum states (which ends up being two aspects of the same thing).
Although there are justifications outside of quantum mechanics if you, for example, already believe in the laws of thermodynamics. If computation didn't create entropy, you could reverse entropy. Of course, now it goes the other way. Since the universe runs on quantum mechanics 'below' thermodynamics, entropy can't be reversed because doing so would imply computation without entropy.
Charge-recovery logic has become a lot less interesting with modern fabrication nodes since dynamic power draw (the part that's due to actual charging and discharging within the circuit) is now a relatively minor part of power dissipation, whereas leakage power has become a lot more important. The main way of lowering leakage power is to simply power off unused areas of the chip, but that doesn't help if you actually have to perform logic. So the whole idea of reversible computing has become a bit of a red herring.
The way I see it, current circuits are running in high temperature thermal equilibrium; there's no chance of operational reversibility at the physical level. That's only possible with near 0K computers probably using superconductors and such. So indeed reversibility should only be relevant in this regime when you're operating near the ultimate energetic limits of computation (and quantum computers of course), not high temperature "thermalized" devices.
You eventually have to rewind, if you ever want to run a second program on your reversible computer.
Ideally you break things into small chunks of computation where you run it forward, copy the result (at some energy cost), then rewind it. Then you're only paying per bit of result.
I’ve been wanting to try that package out! Seeing NiLang discussed in the context of automatic differentiation in the Julia community was a bit mind bending, and the first time I ever heard about reversible computing.
Interesting fact: In a quantum algorithm you can not really delete information, which is why quantum algorithms are always defined as reversible computations (unitary matrices).
Also, here is a reversible programming language someone made (which has nothing to do with quantum):
For anyone interested in the topic I highly recommend checking out Dr. Michael P. Frank's work. This video is good one to start with https://www.youtube.com/watch?v=IQZ_bQbxSXk
Closure under inverse is like the most important idea in math, physics and probability. Linear logic, constructive math, probability, quantum mechanics all have in common that they rely on closure under adjoint and norm which in turn give you closure under inverse.
Following the link to the article about Landauer's principle[0] and then to Koomey's law[1] takes you to a set of facts that have stuck with me for years. Firstly:
> As of 2011, computers have a computing [energy] efficiency of about 0.00001%.
which means that computers could theoretically be made 10 million times more energy efficient. Even more strikingly, though:
> Assuming that the energy efficiency of computing will continue to double every 1.57 years, the Landauer bound will be reached in 2048.
The possibility of seeing a 10 million times increase in energy efficiency in my lifetime is hard to imagine, as indeed is the possibility that the practical limit is reached before 2048.
According to [Michael Frank's video](https://youtu.be/IQZ_bQbxSXk?t=547), there is an architectural overhead of ~500x that people can not get over (IIUC, this overhead only applies for gate based computing models). A reasonable gap between state-of-the-art gate based computing models and Landauer's limit should be 10^2-10^3. On the other side, reversible computing in general has 2-16 times computational overhead at the software level from my using experience. To save energy, reversible computing has to be at least ~10x more energy efficient at the instruction level.
It is not clever to build a completely reversible computer. No one wants to undo the computing to erase the disk after training a neural network for a month. Reversible computing is not always more energy efficient. The "proof" follows from the Bennett's time space tradeoff: https://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Lev...
As the coarse graining process goes, the ratio between computing time and garbadge space size increases exponentially. Erasing space is more energy efficient when E_compute/E_erase > N_uncompute/N_erase, where E and N are energy and number of instructions.
BUT, it is very likely to have a reversible computing device like GPU that can do part of works.
The key point is: most reversible computing devices CAN erase information, although with energy cost. We just need to switch between uncomputing and erasing at the right place. e.g NiLang is an eDSL that lives in function level, while most other reversible programming languages are standalone.
A interesting subject under this is reversible programming languages, there is for example Janus [0], which given some input program can generate the inverse, it can also generate C++ code with both directions.
One of the biographical books attributed to him (The Pleasure of Finding Things Out?) ha a chapter dedicated to this and related concepts. I was astonished when reading it, especially since he discussed this decades ago, but we don't hear much about it today, at least in popular media.
Same. I was introduced to the concept in the book Feynman Lectures on Computation. It's an excellent read. He was a brilliant man and it's fun seeing someone coming at computation from the physical direction.
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.
Since x + y = z can't be reversed without preserving input, this would have to use additional memory. What if you then have z + a = b? Can you now throw out x/y, or does it have to be reversible all the way back to the beginning?
You start with {x, y, z=0, a, b=0} and then reversibly compute z+=x; z+=y, b+=z; b+=a to end up with {x, y, z=x+y, a, b=x+y+a} from which you could reversibly compute the starting state again with b-=a, etc.
You can't. If you want to zero the memory holding the initial values, you have to exchange it with some other memory. This is how current ('non'-reversable) computers work: exchanging junk data with the large number of known-value bits constituting a low-temperature and/or fixed-voltage environment via diffusion (eg, attaching a bit storage location to GND to clear it by diffusing its change into the GND bus + waste heat).
Nice project, please also check this notebook of Billiard ball model cellular automata (BBMCA) in NiLang: https://giggleliu.github.io/NiLang.jl/dev/notebooks/margolus... . BBMCA is a reversible cellular automata model that very possible to find a physical correspondence. It is a strong candidate for future reversible computing in my mind.
York Uni wrote a fully reversible demonstrator for cricket scoring. It might have been somebody's phd in 1983-5 timeframe.
I think the phd was about both language primitives in either ADA or Modula-<something> and compiler/runtime support. The demonstrator let you fix up mistakes in runs and scoring.
(Cricket has this thing called duckworth-lewis for working out who WOULD have won, formally, for a truncated game, in some arcane process, One of Duckworth or Lewis is a founder of Operations-Research)
In the real world, computers don't start with blank tapes. Whether you can reversibly compress a noisy tape, then, is a question of the tape's entropy. If you can't create blank tape on which to work, you can't do any computing, reversible or otherwise.
one of the benefits of expressing business logic in a high level declarative language like SQL is that the order isn't specified and can be reversed depending on the execution context. a perfectly sargable and streamable view definition for example can end up on either side of a join in some execution plan with data streaming in either direction, and the same code can power filtering as well as generating.
Where order isn't specified, that doesn't mean it can "be reversed". It's just not part of the relevant state. So, I would say that's orthogonal to the issue of reversibility of computing.
fair I guess but that's awfully pedantic. today we can write code that runs backwards and forwards but it's because a compiler is generating multiple versions based on context - if we achieve physical reversibility then maybe one version could do. "computing" has many layers - I don't think it's off topic to include the high level ones in the discussion
It's not "awfully pedantic"; the thing you were talking about has nothing to do with the sort of reversibility being discussed here, other than the name.
got it, "reversible computing" has nothing to do with writing code that can run backwards or forwards, nothing at all, I may as well be talking about the weather and here you guys are trying to have a serious conversation about theoretics ;) I'll see myself out - never change, HN!
There are different senses of "forwards and backwards". There's nothing particularly wrong with yours, there's nothing particularly wrong with the other one, but they aren't the same.
"Reversible computing" here means that you can run it backwards in the sense of undoing what was done by running it forwards.
You're talking about data flowing in opposite directions, while in every case your program runs forwards doing its thing.
P vs NP can be expressed using Turing machines. However, reversible languages like Janus can only execute injective functions whereas a Turing machine can also execute non-injective functions. This is why reversible Turing completeness, or r-Turing completeness, was invented[0] to further work on reversible languages.
As P vs NP has to do with Turing machines, not just reversible Turing machines, it's not really that comparable as far as I know.
There is some comparison that can be made between TMs and RTMs if you have multiple memory tapes, but I forgot what it was. Could be that that was also described in [0], but I don't know.
[0] "What do reversible programs compute?" from Axelsen et al.
While it doesn't relate directly, but quantum computing (which is reversible) is represented by BQP complexity class, which contains P, but it's still unclear how it relates to NP.
I thought a lot about a reversible programming language, a long time ago...
The biggest problem with one is that there would be a huge overhead -- both in execution time and memory used for a truly "reversible" language.
I thought at the stack level back then -- basically one of the things that would need to be accomplished would be that a reversible program would have to store old states of the stack, should they be necessary to be reverted...
But now I'm thinking to myself...
What if the reversibility of a program was implemented at the function level?
In other words, ignore the stack (at least temporarily)... and look at each function (procedure/method/routine -- call it what you will, I'll use the term 'function' to apply to all of them) in terms of the memory that it changes, and only in terms of the memory it changes...
See, a virtual machine that emulates instructions would be great for this... you reprogram on the instruction level, such that:
Did this instruction change memory? Yes? OK, now record that change somewhere, like in a hash that ties this change to this invocation of the function (another point... each function would need a unique "invocation ID"... time consuming to say the least, but that's a sub-discussion)...
So now we know (at the cost of tremendous speed! <g>) which functions changed which memory when!
And of course, if a function say copies a gigabyte worth of data, then not only is the system slow, but that one function invocation -- would waste an extra gigabyte of memory to keep track of that memory's previous state!
But it could be done...
Maybe the solution (or one possible solution) would be to implement "memory change tracking" (for lack of a better term!) at the function level, and so, the program author, via compiler assistance, could determine what functions could be "memory change tracked" and which wouldn't.
Or, you could implement a system where the memory change tracking kicks in at a certain point (say, when you're debugging and know that a vicious bug is imminent, and you want to find out more about it -- so then you turn on the "full reversibility" aspect of your program!)
Or (even better!) -- don't use the VM instruction tracking, add a feature to a compiler to generate additional instructions to do the tracking (much faster than using a VM)...
But, no matter which way, it will be slow, it will consume tons of CPU cycles, and it (depending on what your program does) will eat memory like no tomorrow!
Still... in a development environment, to find a particularly nasty and elusive bug... it might be worth it...
> What if the reversibility of a program was implemented at the function level?
Are you finding NiLang? - an embedded domain specific language in Julia for creating reversible functions. Meanwhile, it has one of the best performance in automatic differentiation (AD).
I find reversible programming particularly useful in the reverse mode AD, where reversing the tape is required in order to use intermediate information to compute gradients. The Bennett's time space trade-off is particularly useful. Traditional AD also have something similar called treeverse to trace back states, however, it involves nasty implicit stack operations and can not utilize reversibility. Reversible computing is way more elegant.
[Edit: the video recommended by gbrown_ elsewhere in this thread (https://news.ycombinator.com/item?id=26295043) refers to this paper and also shows how it is possible to move beyond the constraints introduced in it.]
[1] (PDF) https://www.cs.princeton.edu/courses/archive/fall06/cos576/p...