Turing Machine was invented by Alan Turing in 1936 and it is used to accept Recursive Enumerable Languages (generated by Type-0 Grammar).
A turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions.
A TM is expressed as a 7-tuple (Q, T, B, ∑, δ, q0, F) where:
- Q is a finite set of states
- T is the tape alphabet (symbols which can be written on Tape)
- B is blank symbol (every cell is filled with B except input alphabet initially)
- ∑ is the input alphabet (symbols which are part of input alphabet)
- δ is a transition function which maps Q × T → Q × T × {L,R}. Depending on its present state and present tape alphabet (pointed by head pointer), it will move to new state, change the tape symbol (may or may not) and move head pointer to either left or right.
- q0 is the initial state
- F is the set of final states. If any state of F is reached, input string is accepted.
Let us construct a turing machine for L={0^n1^n|n>=1}
- Q = {q0,q1,q2,q3} where q0 is initial state.
- T = {0,1,X,Y,B} where B represents blank.
- ∑ = {0,1}
- F = {q3}
Transition function δ is given in Table 1 as:
Illustration
Let us see how this turing machine works for 0011. Initially head points to 0 which is underlined and state is q0 as:
Using move δ(q3, B) = halt, it will stop and accepted.
Note:
- In non-deterministic turing machine, there can be more than one possible move for a given state and tape symbol, but non-deterministic TM does not add any power.
- Every non-deterministic TM can be converted into deterministic TM.
- In multi-tape turing machine, there can be more than one tape and corresponding head pointers, but it does not add any power to turing machine.
- Every multi-tape TM can be converted into single tape TM.
