Re:Bitbanging 1D Reversible Automata
by orlp on Friday December 13, 2024 @07:40AM
(#42407978)
A rule R is reversible if there exists a rule R^-1 such that for all a, b, c, d, e, f, g we see the following evolution (where . stands for "don't care"):
In equations, it means there must exist some R^-1 such that for all a, b, c, d, e, f, g the following holds:
Writing a quick program that checks all possible combinations of R and R^-1 (https://play.rust-lang.org/?version=stable&mode=debug&editio...) we find the following inverse pairs:
That is, the following two rules are self-inverses (they're the NOT and IDENTITY gates on the center cell respectively):
We have the left <-> right moving pair you identified:
And there's just one more, which is the same as the above but it also inverts the output (move left and invert is the inverse of move right and invert):
[ Parent
| on HN ]
Very neat, thanks for working this out. (Why would it not be sufficient to start with just five symbols?)
The solution is like a restricted version of Hilbert's Hotel, we're still in a group of invertible maps on binary sequences {0,1}^N but we aren't allowed to do anything non-local.
https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Gra...