Non-deterministic Turing machine (NTM)

A non-deterministic Turing machine is a variant of the simple Turing machine. For every input at a state, there can be multiple paths/actions performed by the TM, meaning the transitions are not deterministic.

The difference between a deterministic TM and a non-deterministic TM is the same as a DFA and an NFA. A multi-tape Turing machine is used to construct an NTM.

Note: To learn more about the simple Turing machine, click here

Formal theorem

The non-deterministic Turing machine is a 6 tuple machine:$(Q, Σ, q_0, \Gamma, δ, F)$

• $Q$- set of states

• $Σ$- set of input alphabets

• $q_0$- initial state

• $\Gamma$- set of tape alphabets

• $δ$- transition function that is

  $Q \space * \Gamma^i \to P(Q \space * \Gamma^i \space * (Left, right, stationary)^i)$

•  $F$- set of final states

In the transition function, the left side of the transition is enclosed in $P$ (power set), which means that a state can move to more than one state on getting a particular input.

Computation tree

All possible transition sequences of a non-deterministic Turing machine on a given input string can be represented by a tree called a computation tree.

For example, for the given Non-deterministic TM:

The computational tree for input $aa$ will be of the sort:

The outcome of a non-deterministic TM

There can be two outcomes for a given non-deterministic TM:

• If any branch accepts the input string, then the NTM also accepts.

• If all the branches halt or reject the input string, the NTM also rejects.