Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


Implementation [of TM cellular automaton]

Given a non-deterministic Turing machine with rules in the form above, the rules for a cellular automaton which emulates it can be obtained from

NDTMToCA[tm_] := Flatten[{{_, h, _} -> h, {s, _c, _} -> e, {s, _, _} -> s, {_, s, c[i_]} -> s[i], {_, s, x_} -> x, {a[_, _], _s, _} -> s, {_, a[x_, y_], s[i_]} -> a[x, y, i], {x_, _s, _} -> x, {_, _, s[i_]} -> s[i], (Table[ With[{b = (#1[[ Min[Length[#1], z]]] &)[{x, #1} /.tm]}, If[Last[b] == -1, {{a[_], a[x, #1, z], e} -> h, {a[_], a[x, #1, z], s} -> a[x, #1, z], {a[_], a[x, #1, z], _} -> a[b[[2]]], {a[ x, #1, z], a[w_], _} -> a[b[[1]], w], {_, a[w_], a[x, #1, z]} -> a[w]}, {{a[_], a[x, #1, z], _} -> a[b[[2]]], {a[ x, #1, z], a[w_], _} -> a[w], {_, a[w_], a[x, #1, z]} -> a[b[[1]], w]}]], {x, Max[(#1[[1, 1]] &) /@ tm]}, {z, Max[(Length[#1[[2]]] &) /@ tm]}] &) /@ Union[(#1[[1, 2]] &) /@ tm], {_, x_, _} -> x}]


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