Turing machines [emulating cellular automata]

Given the rules for an elementary cellular automaton in the form used on page 867, the following will construct a Turing machine which emulates it:

CAToTM[rules_] := {{q[a_, b_], c : (0 | 1)}  {q[b, c], {a, b, c} /. rules, 1}, {q[_, _], x}  {p[0], 0, -1}, {p[a_], b : (0 | 1)}  {p[b], a, -1}, {p[_], x}  {q[0, 0], 0, 1}}

Given a list of initial cell colors for the cellular automaton, the initial tape for the Turing machine consists of Join[{0, 0}, list, {0, 0}] surrounded by x's, with the head of the Turing machine on the first 0 in state q[0, 0].

For specific cellular automata it is often possible to construct smaller Turing machines, as on pages 707 and 1119. By combining identical cases in rules and writing rules as compositions of ones with smaller neighborhoods one can for example readily construct Turing machines with 4 states and 3 colors that emulate 166 of the elementary cellular automata.