Editing Nondeterministic Turing machine (section)

===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.