Editing Nondeterministic Turing machine (section)

==Formal definition==
A nondeterministic Turing machine can be formally defined as a six-tuple <math>M=(Q, \Sigma, \iota, \sqcup, A, \delta)</math>, where
*<math>Q</math> is a finite set of states
*<math>\Sigma</math> is a finite set of symbols (the tape alphabet)
*<math>\iota \in Q</math> is the initial state
*<math>\sqcup \in \Sigma</math> is the blank symbol
*<math>A \subseteq Q</math> is the set of accepting (final) states
*<math>\delta \subseteq \left(Q \backslash A \times \Sigma\right) \times \left( Q \times \Sigma \times \{L,S,R\} \right)</math> is a relation on states and symbols called the ''transition relation''. <math>L</math> is the movement to the left, <math>S</math> is no movement, and <math>R</math> is the movement to the right.

The difference with a standard (deterministic) [[Turing machine]] is that, for deterministic Turing machines, the transition relation is a function rather than just a relation.

Configurations and the ''yields'' relation on configurations, which describes the possible actions of the Turing machine given any possible contents of the tape, are as for standard Turing machines, except that the ''yields'' relation is no longer single-valued. (If the machine is deterministic, the possible computations are all prefixes of a single, possibly infinite, path.)

The input for an NTM is provided in the same manner as for a deterministic Turing machine: the machine is started in the configuration in which the tape head is on the first character of the string (if any), and the tape is all blank otherwise.

An NTM accepts an input string if and only if ''at least one'' of the possible computational paths starting from that string puts the machine into an accepting state.  When simulating the many branching paths of an NTM on a deterministic machine, we can stop the entire simulation as soon as ''any'' branch reaches an accepting state.

===Alternative definitions===
As a mathematical construction used primarily in proofs, there are a variety of minor variations on the definition of an NTM, but these variations all accept equivalent languages.

The head movement in the output of the transition relation is often encoded numerically instead of using letters to represent moving the head Left (-1), Stationary (0), and Right (+1); giving a transition function output of <math>\left( Q \times \Sigma \times \{-1,0,+1\} \right)</math>.  It is common to omit the stationary (0) output,<ref name="GJ">{{cite book|last=Garey|first=Michael R.|author2=David S. Johnson|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|publisher=W. H. Freeman|year=1979|isbn=0-7167-1045-5|url-access=registration|url=https://archive.org/details/computersintract0000gare}}</ref> and instead insert the transitive closure of any desired stationary transitions.

Some authors add an explicit ''reject'' state,<ref name="jeffe">{{cite web |url=http://jeffe.cs.illinois.edu/teaching/algorithms/models/09-nondeterminism.pdf|title=Nondeterministic Turing Machines|last=Erickson|first=Jeff|publisher=U. Illinois Urbana-Champaign|access-date=2019-04-07}}</ref>
which causes the NTM to halt without accepting.  This definition still retains the asymmetry that ''any'' nondeterministic branch can accept, but ''every'' branch must reject for the string to be rejected.