# Definition:Nondeterministic Turing Machine

Jump to navigation
Jump to search

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

## Also see

Note that while a traditional Turing machine can be built or simulated rather easily, a NTM cannot actually be constructed.

- Nondeterministic Turing Machine Equivalent to Deterministic Turing Machine
- Definition:NP Complexity Class

## Source of Name

This entry was named for Alan Mathison Turing.