Coupon Accepted Successfully!


Turing Machines



A turing machine is a 7-tuple (Q, Σ, Γ, δ, q0, qaccept, qreject), where

  1. Q is the set of states.
  2. Σ is the input alphabet not containing the blank symbol,979.png
  3. Γ is the tape alphabet, where 984.png   Γ and Σ Γ.
  4. δ : Q × Γ  Q × Γ × {L, R} is the transition function.
  5. q0   Q is the start state.
  6. qaccept   Q is the accept state.
  7. qreject   Q is the reject state, where qreject  qaccept.

Initially M (turing machine) receives its input w  Σ* on the leftmost n squares of the tape and rest of the tape is blank, i.e. filled with blank symbol. The head starts from the leftmost square of the tape. Once M has started, the computation proceeds according to the rules described by the transition function. If M ever tries to move its head to the left off the left hand end of the tape, the head stays in the same place for that move, even though the transition function indicates L. The transition continues until it enters either the accept or reject states at which point it halts. If neither occurs, M goes on forever. As a TM computes, changes occur in the current state, current tape content and current head location. A setting of these three items is called a CONFIGURATION.


  • The above diagram shows a TM with configuration 10101q7 110.
    Let C1 and C2 be configuration of M. C1 yields C2 if M is in configuration C2 after running M in configuration C1 for one step. Suppose δ(q1, b) = (q2, C, L), then aaq1 bb yields aq2 acb. Let w  Σ* and M be a turing machine. M accepts w if there are configs Co, Ci, ..........., Ck, s.t.
    — Co = q0 w
    — Ci yields Ci + 1 for i = 0, ........., k-1, and
    — Ck contains the accept state qaccept.
  • A Turing Machine M recognizes a language L if M accepts exactly those strings in L.
  • A language L is called recognizable or recursively enumerable if some TM recognizes L.
  • A TM decides a language L if M accepts all strings in L and rejects all strings not in L.
  • A language is called decidable or recursive if some TM decides L.
  • L is decidable if and only if both L and ¬ L are recognizable.

Test Your Skills Now!
Take a Quiz now
Reviewer Name