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, an}, rule], {1}]



Image Source Notebooks:

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