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
An element
means that in state , reading symbol , the machine may write , enter state , and move the head in direction . A configuration may therefore have several successors. The number of successors may vary from configuration to configuration, so the computation of
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 ; otherwise it rejects. If
assigns at most one move to every state–symbol pair, the definition reduces to the deterministic Turing machine.