Definition:Nondeterministic Turing Machine
From ProofWiki
Definition
A Nondeterministic (or Non-deterministic) Turing Machine (NTM) is a variation of the classical Turing machine that relaxes the restriction that all the steps in the machine must be definite.
That is, given a single internal state and a single character being read on the tape the machine may have more then one possible response.
If any sequence of choices puts the machine into a halting state, then the machine stops after $n$ steps, where $n$ is the minimum number of steps needed to put the machine into a halting state.
It is important to note that while a traditional Turing machine can be built or simulated rather easily, a NTM cannot actually be constructed.
Source of Name
This entry was named for Alan Mathison Turing.
