structural:scholar_edition, quality:correction
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 (Q × Σ × { − 1, 0, + 1 }) {\displaystyle \left(Q\times \Sigma \times \{-1,0,+1\}\right)}. It is common to omit the stationary (0) output, and instead insert the transitive closure of any desired stationary transitions.

Some authors add an explicit reject state, 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.