> 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 and answer, so I'd just try enumerating all the rules and seeing which ones invert each other.

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.

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

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