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?
Yes you can do compression, if the text is compressible. The playground [1] has a "run length encoding" example.
Maybe you meant sorting. You can implement sorting algorithms, as long as you store the information which entries were swapped. (To "unsort" the entries when running in reverse). So, an array that is already sorted doesn't need much additional information; one that is unsorted will require a lot of "undo" space. I think this is the easiest example to see the relation between reversible computing and thermodynamics: in thermodynamics, to bring "order" to a system requires "unorder" (heat) somewhere else.
There are also examples for encryption / decryption, but I find compression and sorting more interesting.
You could package all your data into a zip using this language but you would also have a worthless stretch of memory seemingly filled with noise / things you’re not interested in.
Why do you think so? The code example shows that you can do RLE (run length encoding) without noise / additional space. I'm pretty sure you can do zip as well. It would just be very hard to implement, but it wouldn't necessarily require that the output contains noise.
Hmm. As a physicist my intuition is that information-preserving transformations are unitary (unitary transformations are 1-to-1). If a compression algorithm is going to yield a bit string (the zip file, for example) shorter than the original it can't be 1-to-1. So it must yield the zip file and some other stuff to make up for the space saved by the compression.
Actually this is true whichever interpretation you take, give or take some knowledge around black holes.
I think hawking actually proved that this is true regardless of how black holes work due to hawking radiation.
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.
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
So if Toffolli gates can serve as a substrate for NAND and NAND is computationally universal. What happens when I build a hash function out of Trofolli-backed NAND gates? Can I run it in reverse and generate pre-images?
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
44 comments
[1] https://en.wikipedia.org/wiki/Janus_(time-reversible_computi...
Maybe you meant sorting. You can implement sorting algorithms, as long as you store the information which entries were swapped. (To "unsort" the entries when running in reverse). So, an array that is already sorted doesn't need much additional information; one that is unsorted will require a lot of "undo" space. I think this is the easiest example to see the relation between reversible computing and thermodynamics: in thermodynamics, to bring "order" to a system requires "unorder" (heat) somewhere else.
There are also examples for encryption / decryption, but I find compression and sorting more interesting.
[1] https://topps.diku.dk/pirc/?id=janusP
[1] https://topps.diku.dk/pirc/?id=janusP
> The universe is just one gigantic reversible computation.
Assuming that the Many-Worlds interpretation is true.
> 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.
> 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?
Reversible Computing (2016) [video] (youtube.com)
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