Non-Deterministic Turing Machine

In a Non-Deterministic Turing Machine, for every state and symbol, there are a group of actions the TM can have. So, here the transitions are not deterministic. The computation of a non-deterministic Turing Machine is a tree of configurations that can be reached from the start configuration.

An input is accepted if there is at least one node of the tree which is an accept configuration, otherwise it is not accepted. If all branches of the computational tree halt on all inputs, the non-deterministic Turing Machine is called a Decider and if for some input, all branches are rejected, the input is also rejected.

A non-deterministic Turing machine can be formally defined as a 6-tuple (Q, X, ∑, δ, q₀, B, F) where −

Q is a finite set of states

X is the tape alphabet

∑ is the input alphabet

δ is a transition function;

δ : Q × X → P(Q × X × {Left_shift, Right_shift}).

q₀ is the initial state

B is the blank symbol

F is the set of final states