Notes

Chapter 11: The Notion of Computation

Section 6: Emulating Cellular Automata with Other Systems


Multicolor Turing machines [from 2-color TMs]

Given rules in the form on page 888 for a Turing machine with s states and k colors the following yields an equivalent Turing machine with With[{c = Ceiling[Log[2, k]]}, (3 2^c + 2c - 7) s] states (always less than 6.03 k s) and 2 colors:

TMToTM2[rule_, s_, k_] := # /. MapIndexed[# -> First[#2] &, Union[#[[1,1]] & /@ #]] &[ With[{b = Ceiling[Log[2, k]] - 1}, Flatten[Table[{Table[{Table[{{m, i, n, d}, c} -> {{m, Mod[i, 2^(n - 1)], n - 1, d}, Quotient[i, 2^(n - 1)], 1}, {n, 2, b}, {i, 0, 2^n - 1}], Table[{{m, i, 1, d}, c} -> {{m, -1, 1, d}, i, d}, {i, 0, 1}], Table[{{m, -1, n, d}, c} -> {{m, -1, n + 1, d}, c, d}, {n, b - 1}], {{m, -1, b, d}, c} -> {{0, 0, m}, c, d}}, {d, -1, 1, 2}], Table[{{i, n, m}, c} -> {{ i + 2^n c, n + 1, m}, c, -1}, {n, 0, b - 1}, {i, 0, 2^n - 1}], With[{r = 2^b}, Table[If[ i + r c >= k, {}, Cases[rule, ({m, i + r c} -> {x_, y_, z_}) -> ({{i, b, m}, c} -> {{x, Mod[y, r], b, z}, Quotient[y, r], 1})]], {i, 0, r - 1}]]}, {m, s}, {c, 0, 1}]]]]

Some of these states are usually unnecessary, and in the main text such states have been pruned. Given an initial condition {i, list, n} the initial condition for the 2-color Turing machine is

With[{b = Ceiling[Log[2, k]]}, {i, Flatten[IntegerDigits[list, 2, b]], b n}]

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