Notes

Chapter 12: The Principle of Computational Equivalence

Section 10: Intelligence in the Universe


Doubling rules [cellular automata]

Rule (a) is

{{0, 2, _} -> 5, {5, 3, _} -> 5, {5, _, _} -> 1, {_, 5, _} -> 1, {_, 2, _} -> 3, {_, 3, 2} -> 2, {_, 1, 2} -> 4, {_, 4, _} -> 3, {4, 3, _} -> 4, {4, 0, _} -> 2, {_, x_, _} -> x}

and takes 2n^2 + n steps to yield Table[1, {2n}] given input Append[Table[1, {n-1}], 2]. Rule (b) is

{{_, 2, _} -> 3, {_, 1, 2} -> 2, {3, 0, _} -> 1, {3, _, _} -> 3, {_, 3, _} -> 1, {_, x_, _} -> x}

and takes 3n steps. Rule (c) is k=3, r=1 rule 5407067979 and takes 3n-1 steps.


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