Testing for reversibility [in cellular automata]

To show that a cellular automaton is reversible it is sufficient to check that all configurations consisting of repetitions of different blocks have different successors. This can be done for blocks up to length n in a 1D cellular automaton with k colors using

ReversibleQ[rule_, k_, n_] := Catch[Do[If[Length[Union[Table[CAStep[rule, IntegerDigits[i, k, m]], {i, 0, k^m - 1}]]] ≠ k^m, Throw[False]], {m, n}]; True]

For k = 2, r = 1 it turns out that it suffices to test only up to n = 4 (128 out of the 256 rules fail at n = 1, 64 at n = 2, 44 at n = 3 and 14 at n = 4); for k = 2, r = 2 it suffices to test up to n = 15, and for k = 3, r = 1, up to n = 9. But although these results suggest that in general it should suffice to test only up to n = k^{2 r}, all that has so far been rigorously proved is that n = k^{2 r} (k^{2 r}-1) + 2 r + 1 (or n = 15 for k = 2, r = 1) is sufficient.

For 2D cellular automata an analogous procedure can in principle be used, though there is no upper limit on the size of blocks that need to be tested, and in fact the question of whether a particular rule is reversible is directly equivalent to the tiling problem discussed on page 213 (compare page 942), and is thus formally undecidable.