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