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

Bitbanging 1D Reversible Automata

richiejp.com

Post reply on HN
Print view View original

21–24 of 24 posts

Re: Bitbanging 1D Reversible Automata

#21

Post by orlp »

tromp wrote: post #16

The author make automata reversible by xoring with the previous row's cell. But some rules are reversible without this trick. For example rule 0xf0: 111 110 101 100 011 010 001 000 1 1 1 1 0 0 0 0 will shift all cells one step to the right and is thus the reverse of rule 0xaa which shifts all cells to the left: 111 110 101 100 011 010 001 000 1 0 1 0 1 0 1 0 My question is how can we test which of the 256 rules are r…

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"):

    a  b  c  d  e  f  g

       Apply rule R

    .  b' c' d' e' f' .
       
       Apply rule R^-1

    .  .  c  d  e  .  .
In equations, it means there must exist some R^-1 such that for all a, b, c, d, e, f, g the following holds:

    c = R^-1(R(a, b, c), R(b, c, d), R(c, d, e))
    d = R^-1(R(b, c, d), R(c, d, e), R(d, e, f))
    e = R^-1(R(c, d, e), R(d, e, f), R(e, f, g))
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:

   0x33  0x33
   0x55  0x0f
   0xcc  0xcc
   0xf0  0xaa
That is, the following two rules are self-inverses (they're the NOT and IDENTITY gates on the center cell respectively):

    111 110 101 100 011 010 001 000
     0   0   1   1   0   0   1   1
     1   1   0   0   1   1   0   0
We have the left right moving pair you identified:

    111 110 101 100 011 010 001 000
     1   0   1   0   1   0   1   0

    111 110 101 100 011 010 001 000
     1   1   1   1   0   0   0   0
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):

    111 110 101 100 011 010 001 000
     0   1   0   1   0   1   0   1

    111 110 101 100 011 010 001 000
     0   0   0   0   1   1   1   1

Re: Bitbanging 1D Reversible Automata

#23

Post by orlp »

tromp wrote: post #19
Y_Y wrote: post #18

Earlier quoted context omitted.

> My question is how can we test which of the 256 rules are reversible and how do they pair up? I wondered this too. It feel like a generalization of the well-studied deconvolution problem, but thankfully without noise. I haven't had my coffee yet, but some quick googling any thinking didn't deliver an answer, so I'd just try enumerating all the rules and seeing which ones invert each other. Or, take all permutations…

For a rule to be reversible, it should have a 1 in 4 places, ie. hamming weight 4. I suspect all (8 choose 4) = 70 rules might be reversible.

It turns out that only the identity gate and the left right moving rules are reversible, plus their negated variants, see my other comment.

Re: Bitbanging 1D Reversible Automata

#24

Post by Y_Y »

orlp wrote: post #21
tromp wrote: post #16

The author make automata reversible by xoring with the previous row's cell. But some rules are reversible without this trick. For example rule 0xf0: 111 110 101 100 011 010 001 000 1 1 1 1 0 0 0 0 will shift all cells one step to the right and is thus the reverse of rule 0xaa which shifts all cells to the left: 111 110 101 100 011 010 001 000 1 0 1 0 1 0 1 0 My question is how can we test which of the 256 rules are r…

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"): a b c d e f g Apply rule R . b' c' d' e' f' . Apply rule R^-1 . . c d e . . In equations, it means there must exist some R^-1 such that for all a, b, c, d, e, f, g the following holds: c = R^-1(R(a, b, c), R(b, c, d), R(c, d, e)) d = R^-1(R(b, c, d), R(c, d, e), R(…

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

Post reply on HN