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, ∑, δ, q0, 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}).
·
q0 is
the initial state
·
B is the blank
symbol
·
F is the set of
final states