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 2c + 2c - 7) s] states (always less than 6.03 k s) and 2 colors:

TMToTM2[rule_, s_, k_] := # /. MapIndexed[#1 First[#2] &, Union[Map[#1, 1 &, #]]] &[With[{b = Ceiling[Log[2, k]] - 1}, Flatten[Table[{Table[{Table[{{m, i, n, d}, c} {{m, Mod[i, 2n - 1], n - 1, d}, Quotient[i, 2n - 1], 1}, {n, 2, b}, {i, 0, 2n - 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 + 2n c, n + 1, m}, c, -1}, {n, 0, b - 1}, {i, 0, 2n - 1}], With[{r = 2b}, 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}]



Image Source Notebooks:

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