Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tofolli gates are all you need

johndcook.com

Post reply on HN
Print view View original

21–30 of 45 posts

Re: Tofolli gates are all you need

#21

Post by mark_l_watson »

thomasmg wrote: post #15

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 thermo…

That sounds interesting. I just checked out the examples in the Haskell Janus implementation: https://github.com/mbudde/jana

Re: Tofolli gates are all you need

#22

Post by thomasmg »

threatripper wrote: post #17
thomasmg wrote: post #15

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 thermo…

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

Re: Tofolli gates are all you need

#23

Post by evanb »

threatripper wrote: post #17
thomasmg wrote: post #15

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 thermo…

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.

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.

Re: Tofolli gates are all you need

#24

Post by thomasmg »

evanb wrote: post #23
threatripper wrote: post #17

Earlier quoted context omitted.

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.

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

Re: Tofolli gates are all you need

#26

Post by red75prime »

thomasmg wrote: post #15

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 thermo…

> The universe is just one gigantic reversible computation.

Assuming that the Many-Worlds interpretation is true.

Re: Tofolli gates are all you need

#27

Post by sethhovestol »

red75prime wrote: post #26
thomasmg wrote: post #15

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 thermo…

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

Re: Tofolli gates are all you need

#28

Post by gaze »

red75prime wrote: post #26
thomasmg wrote: post #15

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 thermo…

> The universe is just one gigantic reversible computation. Assuming that the Many-Worlds interpretation is true.

You just need unitarity.

Re: Tofolli gates are all you need

#29

Post by codethief »

sethhovestol wrote: post #27
red75prime wrote: post #26

Earlier quoted context omitted.

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

Re: Tofolli gates are all you need

#30

Post by codethief »

quuxplusone wrote: post #19
FartyMcFarter wrote: post #14

Earlier quoted context omitted.

> 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 arbitr…

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.

On the topic of scaling, reversible computations are more energy efficient than non-reversible ones, see also the OP. Outputting the original inputs might seem silly and wasteful superficially but if you discarded them (as "heat"), you'd just be back to building a non-reversible, likely much less efficient gate.
Post reply on HN