Notes

Chapter 12: The Principle of Computational Equivalence

Section 6: Computational Irreducibility


[Examples of] reducible systems

The color of a cell at step t and position x can be found by starting with initial condition

Flatten[With[{w = Max[Ceiling[Log[2, {t, x}]]]}, {2 Reverse[ IntegerDigits[t, 2, w]] + 1, 5, 2 IntegerDigits[x, 2, w] + 2}]]

then for rule 188 running the cellular automaton with rule

{{a : 1 | 3, 1 | 3, _} -> a, {_, 2 | 4, a : 2 | 4} -> a, {3, 5 | 10, 2} -> 6, {1, 5 | 7, 4} -> 0, {3, 5, 4} -> 7, {1, 6, 2} -> 10, {1, 6 | 11, 4} -> 8, {3, 6 | 8 | 10 | 11, 4}-> 9, {3, 7 | 9, 2} -> 11, {1, 8 | 11, 2} -> 9, {3, 11, 2} -> 8, {1, 9 | 10, 4} -> 11, {_, a_ /; a > 4, _} -> a, {_, _, _} ->0}

and for rule 60 running the cellular automaton with rule

{{a : 1 | 3, 1 | 3, _} -> a, {_, 2 | 4, a : 2 | 4} -> a, {1, 5, 4} -> 0, {_, 5, _} -> 5, {_, _, _} -> 0}


From Stephen Wolfram: A New Kind of Science [citation]