Non-Deterministic Turing Machine

Posted By on April 29, 2016

Download PDF
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
Turing Machine

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby