There is a programming language that is reversible: Janus [1]. You could write a (lossless) data compression algorithm in this language, and if run in reverse this would uncompress. In theory you could do all types of computation, but the "output" (when run forward) would need to contain the old state. With reversible computing, there is no erased information. Landauer's principle links information theory with thermodynamics: putting order to things necessarily produces heat (ordering something locally requires "disorder" somewhere else). That is why Toffoli gates are so efficient: if the process is inherently reversible, less heat need to be produced. Arguably, heat is not "just" disorder: it is a way to preserve the information in the system. The universe is just one gigantic reversible computation. An so, if we all live in a simulation, maybe the simulation is written in Janus?
This only holds because the system returns its raw (a, b) inputs unchanged. It doesn't seem like a useful property. Of course we can "reverse any function" if we store the inputs! Reversing here just means yielding back the inputs.
> Reversing here just means yielding back the inputs.
Not quite I think - the example gate they give has (a,b,c) as input and it doesn't return c. So it's not yielding all the inputs back.
Furthermore: if you always returned all the inputs, and also computed other values, the outputs from the gates would be strictly increasing in size, so you wouldn't be able to use a finite set of gates to build a computer of arbitrary size.
These 3 way gates also seem to be part of the recent algorithmic advances in Quantum Computing that have put useful applications in reach sooner than previously expected and it kind of reminds me how AI made a lot of the real gains with math optimizations like dropping to NVFP4 etc it all seems like we have been feeling our way in the dark but just starting to touch things
ok, the Landauer limit defines the minimum energy for a bit flip but I don't see how a Toffoli gate would require less energy for a bit flip let alone come into the region of the Landauer limit. Could someone with more knowledge enlighten us (or at least me)?
The Landauer limit defines minimum energy for a bit *erasure*.
A reversible gate doesn't involve any such erasure and therefore Landauer's principle doesn't apply to it.
What will happen in practice if you do an entirely reversible computation is that you end up with the data you care about and a giant pile of scratch memory that you're going to need to zero out if you ever want to reuse it. Or perhaps you rewind the computation all the way back to the beginning to unscratch the scratch memory but you're going to at least need to pay to copy the output somewhere.
IANAP, but my understanding is that the Landauer limit defines the minimum energy of forcing a unknown bit into a known state. Physics as we know it is fully reversible at the microscale - every possible state have exactly one ancestor state. An irreversible process (that is, one that would force to macroscopically distinguishable states into a single one) is only possible if we conduct the "unknowness" aka entropy away from our computer - i. e. generate heat. Toffoli gate are reversible, and therefore in theory you can implement it in a way that is not subject to the Landauer limit.
Obviously, implementing one as a CMOS gate wouldn't be enough. Reversible gates would be very different. AFAIR they need to have a fan-out of one - you can't just wire an output to two inputs without losing reversibility.
For example all the quantum computing is reversible and really doesn't want qbits to interact (hence get any energy) with the outside. So if you ignore all the supporting apparatus in theory it could work without spending energy. Toffoli gates can be used/realized in quantum computes.
// This code originally started life as a CAM6 simulator written in C
// and Forth, based on the original CAM6 hardware and compatible with
// the brilliant Forth software developed by Toffoli and Margolus. But
// then it took on a life of its own (not to mention a lot of other CA
// rules), and evolved into supporting many other cellular automata
// rules and image processing effects. Eventually it was translated to
// C++ and Python, and then more recently it has finally been
// rewritten from the ground up in JavaScript.
// The CAM6 hardware and Forth software for defining rules and
// orchestrating simulations is thoroughly described in this wonderful
// book by Tommaso Toffoli and Norman Margolus of MIT.
// Cellular Automata Machines: A New Environment for Modeling
// Published April 1987 by MIT Press. ISBN: 9780262200608.
// https://mitpress.mit.edu/9780262526319/cellular-automata-machines/
Michael Frank himself (the subject of the IEEE article "Reversible computing escapes the lab") showed up for the HN discussion and answered questions here:
Hi, someone pointed me at your comment, so I thought I'd reply.
First, the circuit techniques that aren't reversible aren't truly, fully adiabatic either -- they're only quasi-adiabatic. In fact, if you strictly follow the switching rules required for fully adiabatic operation, then (ignoring leakage) you cannot erase information -- none of the allowed operations achieve that.
Second, to say reversible operation "only saves an extra 20%" over quasi-adiabatic techniques is misleading. Suppose a given quasi-adiabatic technique saves 79% of the energy, and a fully adiabatic, reversible version saves you "an extra 20%" -- well, then now that's 99%. But, if you're dissipating 1% of the energy of a conventional circuit, and the quasi-adiabatic technique is dissipating 21%, that's 21x more energy efficient! And so you can achieve 21x greater performance within a given power budget.
Next, to say "resistive losses dominate the losses" is also misleading. The resistive losses scale down arbitrarily as the transition time is increased. We can actually operate adiabatic circuits all the way down to the regime where resistive losses are about as low as the losses due to leakage. The max energy savings factor is on the order of the square root of the on/off ratio of the devices.
Regarding "adiabatic circuits can typically only provide an order of magnitude power savings" -- this isn't true for reversible CMOS! Also, "power" is not even the right number to look at -- you want to look at power per unit performance, or in other words energy per operation. Reducing operating frequency reduces the power of conventional CMOS, but does not directly reduce energy per operation or improve energy efficiency. (It can allow you to indirectly reduce it though, by using a lower switching voltage.)
You are correct that adiabatic circuits can benefit from frequency scaling more than traditional CMOS -- since lowering the frequency actually directly lowers energy dissipation per operation in adiabatic circuits. The specific 4000x number (which includes some benefits from scaling) comes from the analysis outlined in this talk -- see links below - but we have also confirmed energy savings of about this magnitude in detailed (Cadence/Spectre) simulations of test circuits in various processes. Of course, in practice the energy savings is limited by the resonator Q value. And a switched-capacitor design (like a stepped voltage supply) would do much worse, due to the energy required to control the switches.
A modern computer makes billions of calculations per second. The calculations have a "forward direction". For example, if the result of x + y is 4, you cannot "compute backwards" and find out what x and y are equal to.
But calculations can be reversible. For instance one could say that x is 3, and then have enough information to run the calculation backwards. This is particularly interesting because physics dictates that computers based on reversible calculations use less energy than ones based on non-reversible calculations.
Lecturer: Postdoc Holger Bock Axelsen from the Department of Computer Science, University of Copenhagen
There is a programming language that is reversible: Janus [1]. You could write a (lossless) data compression algorithm in this language, and if run in reverse this would uncompress. In theory you could do all types of computation, but the "output" (when run forward) would need to contain the old state. With reversible computing, there is no erased information. Landauer's principle links information theory with thermodynamics: putting order to things necessarily produces heat (ordering something locally requires "disorder" somewhere else). That is why Toffoli gates are so efficient: if the process is inherently reversible, less heat need to be produced. Arguably, heat is not "just" disorder: it is a way to preserve the information in the system. The universe is just one gigantic reversible computation. An so, if we all live in a simulation, maybe the simulation is written in Janus?
[1] https://en.wikipedia.org/wiki/Janus_(time-reversible_computi...
That sounds interesting. I just checked out the examples in the Haskell Janus implementation: https://github.com/mbudde/jana
Could you really do general compression in this language? I was under the impression that the output is always the same size or larger than the input.
> We’re far from the ultimate physical limit, but reversibility still provides practical efficiency gains today.
I'd love to hear more about this. Where it's used today and how big are the gains?
> any Boolean function can be computed reversibly
This only holds because the system returns its raw (a, b) inputs unchanged. It doesn't seem like a useful property. Of course we can "reverse any function" if we store the inputs! Reversing here just means yielding back the inputs.
> Reversing here just means yielding back the inputs.
Not quite I think - the example gate they give has (a,b,c) as input and it doesn't return c. So it's not yielding all the inputs back.
Furthermore: if you always returned all the inputs, and also computed other values, the outputs from the gates would be strictly increasing in size, so you wouldn't be able to use a finite set of gates to build a computer of arbitrary size.
c is the constant 1. You don't need to store that.
> Furthermore [this doesn't scale].
Precisely.
https://en.wikipedia.org/wiki/Toffoli_gate has better details.
1 reply →
These 3 way gates also seem to be part of the recent algorithmic advances in Quantum Computing that have put useful applications in reach sooner than previously expected and it kind of reminds me how AI made a lot of the real gains with math optimizations like dropping to NVFP4 etc it all seems like we have been feeling our way in the dark but just starting to touch things
ok, the Landauer limit defines the minimum energy for a bit flip but I don't see how a Toffoli gate would require less energy for a bit flip let alone come into the region of the Landauer limit. Could someone with more knowledge enlighten us (or at least me)?
The Landauer limit defines minimum energy for a bit *erasure*.
A reversible gate doesn't involve any such erasure and therefore Landauer's principle doesn't apply to it.
What will happen in practice if you do an entirely reversible computation is that you end up with the data you care about and a giant pile of scratch memory that you're going to need to zero out if you ever want to reuse it. Or perhaps you rewind the computation all the way back to the beginning to unscratch the scratch memory but you're going to at least need to pay to copy the output somewhere.
IANAP, but my understanding is that the Landauer limit defines the minimum energy of forcing a unknown bit into a known state. Physics as we know it is fully reversible at the microscale - every possible state have exactly one ancestor state. An irreversible process (that is, one that would force to macroscopically distinguishable states into a single one) is only possible if we conduct the "unknowness" aka entropy away from our computer - i. e. generate heat. Toffoli gate are reversible, and therefore in theory you can implement it in a way that is not subject to the Landauer limit.
Obviously, implementing one as a CMOS gate wouldn't be enough. Reversible gates would be very different. AFAIR they need to have a fan-out of one - you can't just wire an output to two inputs without losing reversibility.
For example all the quantum computing is reversible and really doesn't want qbits to interact (hence get any energy) with the outside. So if you ignore all the supporting apparatus in theory it could work without spending energy. Toffoli gates can be used/realized in quantum computes.
*Toffoli
I'm always surprised at the high frequency of major typos in titles from HN posts
Cellular Automata Machines: A New Environment for Modeling, by Tommaso Toffoli and Norman Margolus
https://donhopkins.com/home/cam-book.pdf
CAM6 Demo:
https://www.youtube.com/watch?v=LyLMHxRNuck
Demo of Don Hopkins' CAM6 Cellular Automata Machine simulator.
Live App: https://donhopkins.com/home/CAM6
Github Repo: https://github.com/SimHacker/CAM6
Javacript Source Code: https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
Comments from the code:
Sounds like a type of pasta
Michael Frank himself (the subject of the IEEE article "Reversible computing escapes the lab") showed up for the HN discussion and answered questions here:
Reversible computing escapes the lab (ieee.org)
https://news.ycombinator.com/item?id=42660606
mikepfrank on Jan 14, 2025 | parent | next [–]
Hi, someone pointed me at your comment, so I thought I'd reply. First, the circuit techniques that aren't reversible aren't truly, fully adiabatic either -- they're only quasi-adiabatic. In fact, if you strictly follow the switching rules required for fully adiabatic operation, then (ignoring leakage) you cannot erase information -- none of the allowed operations achieve that.
Second, to say reversible operation "only saves an extra 20%" over quasi-adiabatic techniques is misleading. Suppose a given quasi-adiabatic technique saves 79% of the energy, and a fully adiabatic, reversible version saves you "an extra 20%" -- well, then now that's 99%. But, if you're dissipating 1% of the energy of a conventional circuit, and the quasi-adiabatic technique is dissipating 21%, that's 21x more energy efficient! And so you can achieve 21x greater performance within a given power budget.
Next, to say "resistive losses dominate the losses" is also misleading. The resistive losses scale down arbitrarily as the transition time is increased. We can actually operate adiabatic circuits all the way down to the regime where resistive losses are about as low as the losses due to leakage. The max energy savings factor is on the order of the square root of the on/off ratio of the devices.
Regarding "adiabatic circuits can typically only provide an order of magnitude power savings" -- this isn't true for reversible CMOS! Also, "power" is not even the right number to look at -- you want to look at power per unit performance, or in other words energy per operation. Reducing operating frequency reduces the power of conventional CMOS, but does not directly reduce energy per operation or improve energy efficiency. (It can allow you to indirectly reduce it though, by using a lower switching voltage.)
You are correct that adiabatic circuits can benefit from frequency scaling more than traditional CMOS -- since lowering the frequency actually directly lowers energy dissipation per operation in adiabatic circuits. The specific 4000x number (which includes some benefits from scaling) comes from the analysis outlined in this talk -- see links below - but we have also confirmed energy savings of about this magnitude in detailed (Cadence/Spectre) simulations of test circuits in various processes. Of course, in practice the energy savings is limited by the resonator Q value. And a switched-capacitor design (like a stepped voltage supply) would do much worse, due to the energy required to control the switches.
https://news.ycombinator.com/item?id=43848398
https://www.youtube.com/watch?v=rVmZTGeIwnc
A modern computer makes billions of calculations per second. The calculations have a "forward direction". For example, if the result of x + y is 4, you cannot "compute backwards" and find out what x and y are equal to.
But calculations can be reversible. For instance one could say that x is 3, and then have enough information to run the calculation backwards. This is particularly interesting because physics dictates that computers based on reversible calculations use less energy than ones based on non-reversible calculations.
Lecturer: Postdoc Holger Bock Axelsen from the Department of Computer Science, University of Copenhagen
>p. 99 of "Theory of Self-Reproducing Automata":- API Reference
- Hacker News RSS
- Source on GitHub
- Support Ukraine
- Equal Justice Initiative
- GiveWell Charities
>Von Neumann had been interested in the applications of probability theory throughout his career; his work on the foundations of quantum mechanics and his theory of games are examples. When he became interested in automata, it was natural for him to apply probability theory here also. The Third Lecture of Part I of the present work is devoted to this subject. His "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components" is the first work on probabilistic automata, that is, automata in which the transitions between states are probabilistic rather than deterministic. Whenever he discussed self-reproduction, he mentioned mutations, which are random changes of elements (cf. p. 86 above and Sec. 1.7.4.2 below). In Section 1.1.2.1 above and Section 1.8 below he posed the problems of modeling evolutionary processes in the framework of automata theory, of quantizing natural selection, and of explaining how highly efficient, complex, powerful automata can evolve from inefficient, simple, weak automata. A complete solution to these problems would give us a probabilistic model of self-reproduction and evolution. [9]
[9] For some related work, see J. H. Holland, "Outline for a Logical Theory of Adaptive Systems", and "Concerning Efficient Adaptive Systems".
https://www.deepdyve.com/lp/association-for-computing-machin...
https://deepblue.lib.umich.edu/bitstream/handle/2027.42/5578...
Slacker News
Product
Community