Hacker News Reader

Comment by thomasmg | Hacker News Reader

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

View on HN

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.

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

He meant lossy compression

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

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.

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

(This is way beyond my area of expertise so excuse me that this might be a stupid idea.)

I assume the following happens: while a (small) subsystem is in "pure state" (in quantum coherence), no information flows out of this subsystem. Then, when measuring, information flows out and other information flows in, which disturbs the pure state. This collapses of the wave function (quantum decoherence). For all practical purposes, it looks like quantum decoherence is irreversible, but technically this could still be reversible; it's just that the subsystem (that is in coherence) got much, much larger. Sure, for all practical purposes it's then irreversible, but for us most of physics anyway looks irreversible (eg. black holes).

The problem is that the larger subsystem includes an observer in a superposition of states of observing different measured values. And we never observe this. Copenhagen interpretation doesn't deal with this at all. It just states this empirical fact.

So if I understand correctly, you are saying the observer doesn't feel like he is in a superposition (multiple states at once). Sure: I agree that observers never experience being in a superposition.

But don't think that necessarily means we are in a Many-Worlds. I rather think that we don't have enough knowledge in this area. Assuming we live in a simulation, an alternative explanation would be, that unlikely branches are not further simulated to save energy. And in this case, superposition is just branch prediction :-)

Yes, I think that's a stance many physicists take these days. Unfortunately, it's not verifiable. And we also don't have any clue how gravity (which does become relevant at our scales) would fit into this picture.

You just need unitarity.

Unitarity means that information (about quantum states) is not lost, despite it appearing otherwise after a measurement. The Many-Worlds interpretation seems to be the simplest way to explain where this information has gone.

Reply on news.ycombinator.com