Alan Turing introduced a new mathematical model called the Turing Machine which is a modified version of the PDA and is much more powerful than the PDA.
A PDA is not powerful enough to recognize context-sensitive languages like {a”, b”, c”: n€ N}, but Turing Machine is a generalized machine which can recognize all types of languages viz; regular languages (generated from regular grammar) context-free languages (generated from context-free grammar), context-sensitive languages (generated from context-sensitive grammar) and also the language generated from unrestricted grammar. It is a hypothetical machine, which can simulate any computer algorithm, no matter how complicated it is.
What is Turing Machine?
A TM (Turing machine) is a finite-state machine with infinite tape and a tape head that can read or write.
Definition:
A Turing Machine (TM) is a seven tuple
M = (Q, E, T, S, q, B, F)
Where,
Q-Set of finite states.
Σ - Set of input symbols. (Σ is a subset of I, excluding B)
Ï„ - Set of tape symbols
8 - Transitions from Qxτ→ Qxτ x {L, R}
q. ε Q is a the start state of M.
B is a special symbol indicating blank character.
FCQ is a set of final states.
Transitions: The transition function accepts two parameters namely a state, and a tape symbol and returns a new state after changing the tape symbol and positions read/write head, to the left or right.
The transition function has the form,
8 (state, tape symbol) = (next state, tape symbol, move towards Left/Right)
Types of Turing Machine
There are a number of other types of Turing machines in addition to the one we have already seen, such as turning machines with multiple tapes, turning machines having one tape but with multiple heads, Turing machines with two-dimensional tapes, non-deterministic turning machines etc. All these turning machines are equally powerful. That is, what one type of turning machine computes any other can also compute the same.
1. Multi-tape TM
Multi-tape Turing machines have multiple tapes where each tape is accented with a separate head. It consists of a finite control with K – tape heads and K – tapes) (Each tape is infinite in both directions) (Each head can move independently of the other heads. Initially, the input is on tape and others are blank. At first, the first tape is amused by the input and the other tapes are kept blank. Next, the machine reads successive symbols under its heads and the TM prints a symbol on each tape and moves its head. On a single move depending upon the state of the finite control and the symbol scanned by each of the tapes heads the machine can
• Change the state
• Print a new symbol on each of the cells scanned by its tape heads.
• Move each of its tape heads independently from one cell to the left or right.
2. Non-deterministic TM
A non-deterministic TM is a generalization of the standard TM for which every configuration may yield none or one or more than one next configuration. In contrast to the deterministic Turing machines, for which computation is a sequence of configurations, i.e., a computation of a non-deterministic TM is a tree of configurations that can be reached from the start configuration. For a given state and the tape symbol observed by the tape head, the machine has a finite number of choices for the next move. Each choice consists of a unique state, a tape symbol to print and a direction of head motion. If the input is accepted at least by one path among all the different possible paths, then the input is accepted by the TM.
3. Multi-dimensional TM
(Multi-dimensional TM has a finite control, (a tape which consists of a K-dimensional array of cells which is infinite in all 2K directions.)
Depending on the states and the symbol scanned, the device changes state, prints a new symbol, and moves its head to one of the 2K directions either positively or negatively. Initially, the input is along one axis and the head is at the left end of the input.
4. Multi-head TM
A multi-head TM is a single tape TM with multiple read-write heads. Yet, in every state, only one head may be used. The heads are numbered from 1 to K. Therefore for K heads we have a partition of states Q, Q……Where each Q, contains the set of states which use the ith head) The move of the TM (Turing machine) depends on the state and on the mark scanned by each head. In one move the heads may move independently to the left or to the right.