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], Map[Table[With[{b = (#Min[Length[#], z] &)[{x, #} /. tm]}, If[Last[b] -1, {{a[_], a[x, #, z], e} h, {a[_], a[x, #, z], s} a[x, #, z], {a[_], a[x, #, z], _} a[b2], {a[x, #, z], a[w_], _} a[b1, w], {_, a[w_], a[x, #, z]} a[w]}, {{a[_], a[x, #, z], _} a[b2], {a[x, #, z], a[w_], _} a[w], {_, a[w_], a[x, #, z]} a[b1, w]}]], {x, Max[Map[#1, 1 &, tm]]}, {z, Max[Map[Length[#2] &, tm]]}] &, Union[Map[#1, 2 &, tm]]], {_, x_, _} x}]



Image Source Notebooks:

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