Comment by thomasmg
4 hours ago
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
> The universe is just one gigantic reversible computation.
Assuming that the Many-Worlds interpretation is true.
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.
> Actually this is true whichever interpretation you take
In the Copenhagen interpretation the collapse of the wave function explicitly violates unitarity (and thus reversibility).
You just need unitarity.
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.
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.
[1] https://topps.diku.dk/pirc/?id=janusP
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.
[1] https://topps.diku.dk/pirc/?id=janusP