Nondeterministic Turing Machine

Definition

Nondeterministic Turing Machine

A nondeterministic Turing machine is a Turing machine whose transition relation may assign several moves to one state–symbol pair: instead of a transition function it uses a finite relation

$$\delta \subseteq Q\times \Gamma \times Q\times \Gamma \times D,D=\{L,R,S\}.$$

An element $(q,X;p,Y,d)\in \delta$ means that in state $q$, reading symbol $X$, the machine may write $Y$, enter state $p$, and move the head in direction $d$.

A configuration may therefore have several successors. The number of successors may vary from configuration to configuration, so the computation of $M$ on an input is a general branching tree of configurations, not necessarily a binary tree. The machine accepts an input if some path from the start configuration reaches an accepting state $q\in F$; otherwise it rejects.

If $\delta$ assigns at most one move to every state–symbol pair, the definition reduces to the deterministic Turing machine.