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[d1, 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.