Turing Machine

Turing machine is a mathematical model having tape contain infinite number of cells.

This tape contains a pointers called Read / Write head.

Example Suppose (a) is string after reading a it will replace by (x) or any other character / symbol which is write operation.

R/W head is movable towards right to left or left to right. So we can say that Turing machine is two way.

Each cells contain symbols, symbol means tap symbol.

Tape symbol: Symbol stored in tap is called tape symbol.

Turing machine read tape symbol as well as write tape symbol.

Formal Definition of Turing Machine:

Turing machine is a set of seven tuples.

Tm = (Q , Σ , 𝜏 , q0 , B , F ,δ)

Q → is set of states

Σ → is a set of input symbol such as [a,b]

𝜏 → is a set of tape symbol such as [a,b,x,y,B]

q0 → is a initial state.

B → Blank symbol (here ε is not used)

F → is a set of final state.

δ : Q x 𝜏 → Q x 𝜏 (R,L)

Example : Construct a turing machine for aⁿbⁿ | n>=1

Solution:

aⁿbⁿ

L={ab, aabb, aaabbb, ......}

Note :L here concept of ∈ is removed here B is used after string is ended.

Here a is replaced with suppose X and B is replaced with suppose Y.

For understanding turing machine let we take one example:

Initially the read write head will scan the first symbol of the input string which is a , We have to match first a and first b so for that matching process we have to use two symbols x and y. So a must be replaced by x than we move forward and c will be replaced by y.

After matching a and b we need to move left until we have seen x than again second a and b must be replaced. The above diagram show all moves and replacements.

So for doing this we need to create a turing machine table (δ) for that.

Initially turing m/c start state is q₀. First R/W head scanning symbol a towards right side as show in the above figure, now a will be replaced by x and the state will be q₁. In above table it shown.

In second move we get a so we will not change or replace tape symbol or state.