But the problem is that except in cases where the behavior as a whole is very simple it tends not to be true that systems in fact evolve to strictly invariant states.

But the same is not true of systems like rule 30.

And indeed this is true of any system.

Binary decision diagrams One can specify a Boolean function of n variables by giving a finite automaton (and thus a network) in which paths exist only for those lists of values for which the function yields True .

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 .

With odd n the same turns out to be true for sequences Exp[2 π  Mod[Range[n] 2 , n]/n] —a fact used in the design of acoustic diffusers (see page 1183 ).

But when the form of the true solution is more complicated, such proofs are typically impossible.

Searching for logic [axioms] For axiom systems of the form {…  a} one finds: {((b ∘ b) ∘ a) ∘ (a ∘ b)  a} allows the k = 3 operator 15552 for which the Nand theorem (p ∘ p) ∘ q  (p ∘ q) ∘ q is not true. {(((b ∘ a) ∘ c) ∘ a) ∘ (a ∘ c)  a} allows the k = 4 operator 95356335 for which even p ∘ q  q ∘ p is not true.

And as the pictures below show, this is true even just for parts of the rules above ( s alone yields outer totalistic code 686 in 2D, and rule 90 in 1D).

For rule 30, h μ tx < 1.155 , and there is some evidence that its true value may actually be 1.