Reversible Computing
en.wikipedia.org
en.wikipedia.org
[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...
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 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).
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.
Under quantum mechanics, information may not be destroyed, only moved around (this is implied by the fancy physics/math term 'unitarity').
When you 'destroy' a bit in your (sub-)system, you’re actually transferring that bit into the surrounding environment, which shows up as heat.
Reversible computing avoids that heat generation by keeping all relevant state within your subsystem.
The terminology around 'destroying information' can be confusing because the particular system under discussion isn’t always clear.
Also, here is a reversible programming language someone made (which has nothing to do with quantum):
I wrote something on the topic but it's very incomplete https://github.com/adamnemecek/adjoint
> 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.
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.
[0]: https://en.m.wikipedia.org/wiki/Janus_(time-reversible_compu...
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?
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.
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).
1) Perform some reversible operation
2) Copy answer to another location (At some cost in heat)
3) Perform reverse operation, which rolls back memory to starting point
When you're done you have zeroed out memory, and the only costly operation was the copying of the answer.
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)
"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.
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.
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...
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.
Update: Looks like the related HN discussion is here:
"Nilang.jl – A Reversible Julia DSL":
https://news.ycombinator.com/item?id=24743813
https://github.com/GiggleLiu/NiLang.jl
(Worth it, in my opinion, for the chart showing the "reversed-functions/variables" preceeded by '∂', i.e., ∂x, ∂y, ∂sqxN, etc.)
But anyway, NiLang definitely looks interesting!