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}



Image Source Notebooks:

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