Notes

Chapter 11: The Notion of Computation

Section 5: Emulating Other Systems with Cellular Automata


Turing machines [from cellular automata]

Given any Turing machine with rules in the form used on page 888 and k possible colors for each cell, a cellular automaton which emulates it can be constructed using

TMToCA[rules_, k_:2] := Flatten[{Map[g[#, k]&, rules], {_, x_, _} -> x}] g[{s_, a_} -> {sp_, ap_, d_}, k_] := {If[d==1, Identity, Reverse] [{k s + a, x_, _}] -> k sp + x, {_, k s + a, _} -> ap}

If the Turing machine has s states for its head, then the cellular automaton has k (s+1) colors for each cell. An initial condition with a single cell of color k surrounded by 0's corresponds to being in state 1 with a blank tape in the Turing machine.

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