\begin{definition}[Definition:Nondeterministic Turing Machine]
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.
\end{definition}