Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


Non-deterministic Turing machines

Generalizing rules from page 888 by making each right-hand side a list of possible outcomes, the list of configurations that can be reached after t steps is given by

NTMEvolve[rule_, inits_, t_Integer] := Nest[Union[Flatten[Map[NTMStep[rule, #] &, #], 1]] &, inits, t] NTMStep[rule_List, {s_, a_, n_}] /; (1 <= n <= Length[a]) := Apply[{#1, ReplacePart[a, #2, n], n + #3} &, Replace[{s, a[[n]]}, rule], {1}]


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