Definition:Nondeterministic Turing Machine

From ProofWiki
Jump to navigation Jump to search


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.

Also see

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.