10 ms·

Reversible Computing

149 points by ve55 6y ago

gbrown_ 6y ago
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 https://www.youtube.com/watch?v=IQZ_bQbxSXk
- rpmuller 6y ago
  Michael is great. Here's a link to Michael's Sandia National Labs website, which has links to some of his publications: https://cfwebprod.sandia.gov/cfdocs/CompResearch/templates/insert/profile.cfm?mpfrank https://cfwebprod.sandia.gov/cfdocs/CompResearch/templates/i...
- mikepfrank 6y ago
  Thanks for the plug! :D
m463 6y ago
Feynman was the first person I heard talk about this, pretty interesting topic.
- the__alchemist 6y ago
  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.
  - abdullahkhalids 6y ago
    He also has The Feynman Lectures on Computing, which has a chapter on reversible computing.
- User23 6y ago
  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.
fallingknife 6y ago
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?
- tromp 6y ago
  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.
  - KingFelix 6y ago
    Thanks for this
  - fallingknife 6y ago
    Right, but when can you throw out your initial values? Because if this is going to be usable you have to free up memory sometime.
    - ravi-delia 6y ago
      It goes something like this: 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.
    - a1369209993 6y ago
      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).
adamnemecek 6y ago
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. I wrote something on the topic but it's very incomplete https://github.com/adamnemecek/adjoint https://github.com/adamnemecek/adjoint
corysama 6y ago
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.
- rhn_mk1 6y ago
  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). https://en.wikipedia.org/wiki/No-cloning_theorem https://en.wikipedia.org/wiki/No-cloning_theorem
  - tlb 6y ago
    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.
  - smallnamespace 6y ago
    Just to offer a slightly different rewording that may be more intuitive: 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.
miguelrochefort 6y ago
How does that relate to P versus NP problem?
- wizzwizz4 6y ago
  It doesn't. (Probably.)
- float4 6y ago
  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.
- karlicoss 6y ago
  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.
erk__ 6y ago
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. [0]: https://en.m.wikipedia.org/wiki/Janus_(time-reversible_computing_programming_language) https://en.m.wikipedia.org/wiki/Janus_(time-reversible_compu...
MichaelBurge 6y ago
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?
- einpoklum 6y ago
  > 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.
  - nfoz 6y ago
    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.
- wizzwizz4 6y ago
  It actually does let you do that. Trouble is, unless you can reverse your backup tapes to their original state, that won't help you.
- gnramires 6y ago
  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).
longemen3000 6y ago
In Julia there is a package for a reversible computing DSL, with excelent examples https://giggleliu.github.io/NiLang.jl/dev/ https://giggleliu.github.io/NiLang.jl/dev/
- cbkeller 6y ago
  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.
fmihaila 6y ago
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 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/papers/fredkin_toffoli82.pdf https://www.cs.princeton.edu/courses/archive/fall06/cos576/p...
gfody 6y ago
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.
- einpoklum 6y ago
  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.
  - gfody 6y ago
    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
    - gjm11 6y ago
      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.
      - gfody 6y ago
        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!
        6y ago
jaggirs 6y ago
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): https://wiki.c2.com/?ReversibleProgrammingLanguage https://wiki.c2.com/?ReversibleProgrammingLanguage
- jessriedel 6y ago
  Yes. Another way to put it is that reversible computing is a necessary but not sufficient condition for (universal) quantum computing.
gaogao 6y ago
Humorous, unconventional example of reversible computing using actual swarms of crabs - https://www.wired.com/2012/04/soldier-crabs/ https://www.wired.com/2012/04/soldier-crabs/
omazurov 6y ago
For weekend's entertainment: making Game of Life time reversible. Isotropically. https://github.com/OlegMazurov/Janus https://github.com/OlegMazurov/Janus
- GiggleLiu 6y ago
  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.html 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.
dane-pgp 6y ago
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. [0] https://en.wikipedia.org/wiki/Landauer's_principle https://en.wikipedia.org/wiki/Landauer's_principle [1] https://en.wikipedia.org/wiki/Koomey's_law https://en.wikipedia.org/wiki/Koomey's_law
- GiggleLiu 6y ago
  According to [Michael Frank's video](https://youtu.be/IQZ_bQbxSXk?t=547 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.
ouid 6y ago
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.
Darmody 6y ago
I submitted this a while ago. https://news.ycombinator.com/item?id=19614766 https://news.ycombinator.com/item?id=19614766
ggm 6y ago
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)
peter_d_sherman 6y ago
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...
- GiggleLiu 6y ago
  > 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.
GiggleLiu 6y ago
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/LevineSherman_Tradeoff.pdf 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.

149 points by ve55 6y ago

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 https://www.youtube.com/watch?v=IQZ_bQbxSXk

rpmuller 6y ago
Michael is great. Here's a link to Michael's Sandia National Labs website, which has links to some of his publications: https://cfwebprod.sandia.gov/cfdocs/CompResearch/templates/insert/profile.cfm?mpfrank https://cfwebprod.sandia.gov/cfdocs/CompResearch/templates/i...
mikepfrank 6y ago
Thanks for the plug! :D

m463 6y ago

Feynman was the first person I heard talk about this, pretty interesting topic.

the__alchemist 6y ago
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.
- abdullahkhalids 6y ago
  He also has The Feynman Lectures on Computing, which has a chapter on reversible computing.
User23 6y ago
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.

fallingknife 6y ago

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?

tromp 6y ago
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.
- KingFelix 6y ago
  Thanks for this
- fallingknife 6y ago
  Right, but when can you throw out your initial values? Because if this is going to be usable you have to free up memory sometime.
  - ravi-delia 6y ago
    It goes something like this: 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.
  - a1369209993 6y ago
    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).

adamnemecek 6y ago

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. I wrote something on the topic but it's very incomplete https://github.com/adamnemecek/adjoint https://github.com/adamnemecek/adjoint

corysama 6y ago

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.

rhn_mk1 6y ago
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). https://en.wikipedia.org/wiki/No-cloning_theorem https://en.wikipedia.org/wiki/No-cloning_theorem
- tlb 6y ago
  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.
- smallnamespace 6y ago
  Just to offer a slightly different rewording that may be more intuitive: 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.

miguelrochefort 6y ago

How does that relate to P versus NP problem?

wizzwizz4 6y ago
It doesn't. (Probably.)
float4 6y ago
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.
karlicoss 6y ago
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.

erk__ 6y ago

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. [0]: https://en.m.wikipedia.org/wiki/Janus_(time-reversible_computing_programming_language) https://en.m.wikipedia.org/wiki/Janus_(time-reversible_compu...

MichaelBurge 6y ago

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?

einpoklum 6y ago
> 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.
- nfoz 6y ago
  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.
wizzwizz4 6y ago
It actually does let you do that. Trouble is, unless you can reverse your backup tapes to their original state, that won't help you.
gnramires 6y ago
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).

longemen3000 6y ago

In Julia there is a package for a reversible computing DSL, with excelent examples https://giggleliu.github.io/NiLang.jl/dev/ https://giggleliu.github.io/NiLang.jl/dev/

cbkeller 6y ago
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.

fmihaila 6y ago

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 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/papers/fredkin_toffoli82.pdf https://www.cs.princeton.edu/courses/archive/fall06/cos576/p...

gfody 6y ago

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.

einpoklum 6y ago
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.
- gfody 6y ago
  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
  - gjm11 6y ago
    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.
    - gfody 6y ago
      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!
      - 6y ago

jaggirs 6y ago

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): https://wiki.c2.com/?ReversibleProgrammingLanguage https://wiki.c2.com/?ReversibleProgrammingLanguage

jessriedel 6y ago
Yes. Another way to put it is that reversible computing is a necessary but not sufficient condition for (universal) quantum computing.

gaogao 6y ago

Humorous, unconventional example of reversible computing using actual swarms of crabs - https://www.wired.com/2012/04/soldier-crabs/ https://www.wired.com/2012/04/soldier-crabs/

omazurov 6y ago

For weekend's entertainment: making Game of Life time reversible. Isotropically. https://github.com/OlegMazurov/Janus https://github.com/OlegMazurov/Janus

GiggleLiu 6y ago
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.html 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.

dane-pgp 6y ago

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. [0] https://en.wikipedia.org/wiki/Landauer's_principle https://en.wikipedia.org/wiki/Landauer's_principle [1] https://en.wikipedia.org/wiki/Koomey's_law https://en.wikipedia.org/wiki/Koomey's_law

GiggleLiu 6y ago
According to [Michael Frank's video](https://youtu.be/IQZ_bQbxSXk?t=547 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.

ouid 6y ago

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.

Darmody 6y ago

I submitted this a while ago. https://news.ycombinator.com/item?id=19614766 https://news.ycombinator.com/item?id=19614766

ggm 6y ago

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)

peter_d_sherman 6y ago

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...

GiggleLiu 6y ago
> 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.

GiggleLiu 6y ago

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/LevineSherman_Tradeoff.pdf 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.