Notes

Chapter 11: The Notion of Computation

Section 5: Emulating Other Systems with Cellular Automata


Multiplication systems [from cellular automata]

The rules for the cellular automaton shown here are

{{_, 0, 3 | 8} -> 5, {_, 0, 2 | 7} -> 8, {_, 1, 4 | 9} -> 9, {_, 1, 3 | 8} -> 4, {_, 1, 2 | 7} -> 8, {_, 10, 4 | 9} -> 3, {_, 10, 3 | 8} -> 7, {_, 10, 2 | 7} -> 2, {5 | 6, 1, 0} -> 9, {5 | 6, 10, 0} -> 3, {5 | 6, 1, _} -> 6, {5 | 6, 10, _} -> 5, {_, 2 | 3 | 4 | 5, _} -> 10, {_, 6 | 7 | 8 | 9, _} -> 1, {_, x_, _} -> x}

and the initial condition consists of a single 3 surrounded by 0's. The idea used is that multiplication by 3 can be achieved by scanning digits from right to left, adding to each digit the value of the digit on its immediate right, as well as a carry that can propagate any distance but cannot be larger than 1. Note that as discussed on page 614 multiplication by some multipliers in some bases (such as by 3 in base 6) can be achieved by a single step in the evolution of a suitable cellular automaton. After t steps, the width of the pattern shown here is about Sqrt[Log[2, 3] t]. (See also page 119.)

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