Turing Machine : Introduction

   Turing Machine [TM]

This machine was introduced by Alan Turing in 1936. Turing machine can be constructed to accept a given language or to carry out some algorithm. Unlike of computer, TM has no limitation on the amount of time or memory available for a computation. 

We can compare different machines which are -

Language defined by	Acceptor or recognizer	Non-determinism = Determinism?	Ex. Of application
1.   Regular Expression	Finite Automata	Yes	Text editors
2.   Context free grammar	Pushdown Automata	No	Programming languages, statements, compilers
3.   Type 0 grammar (Unrestricted)	Turing Machine	Yes	Computers

 

Turing Machine Model :

          Fig. shows TM model. The TM model consists of a finite control, an input tape which is divided into cells and a tape head that scans one cell of the tape at a time. Tape is infinite to right. Each cell can contain maximum one-tape symbols. TM works as follows :

           Tape contains input-string w. Let |w| = n ( n symbols) and remaining tape cells contains blank symbol, which is a special tape symbol and not an input symbol.

Move of TM :

i. Changes state

ii. Prints a symbol on the tape cell scanned, replacing previous symbol.

iii. Moves head to left(L) or right(R).

Definition :

         A Turing Machine is a 7-tuple, M = ( Q, Σ,  Γ, δ, q₀ , B, F) 

where, 

i.        Q is the set of states

ii.       Σ is the input alphabet not containing the special blank symbol and Σ ⊆ Γ - {B}

iii.      Γ is a finite set of tape symbols where   B ∈ Γ and Σ ⊆ Γ

iv.      δ is a transition function mapping the states of FA and tape symbols to states, tape symbols and              movement of the head i.e  δ: Q × Γ → Q × Γ × {L, R} 

v.       q₀ ∈ Q is the initial state

vi.      B ∈ Γ is the blank symbol

vii.     F ⊆ Q is a set of final states

Instantaneous Description (ID) 

        Instantaneous Description of TM M, is a string α q: β where q: ∈ Q is present state of M. α β ∈ Γ* is input string and if the first symbol of β is current symbol a, tape head is scanning, then α is a substring formed by all symbols to the left of a.

Consider the fig. We can write ID as  a b a q3 a b b then α = aba and β = abb where head is scanning a.

We assume Q and Γ are disjoint and tape head assumed to be scanning leftmost symbol of α2. If α2 = ∈ the head is scanning blank.

Moves in TM  

      Let x₁x₂…..x_n is an input string to be processed and present symbol under tape head is x_i. 

Let δ(q, x_i) = (p, y, L)

So ID before processing x_i  is x₁ x₂…..x_i-1 , q x_i x_i+1….x_n   after processing  x_i , the resulting ID is x₁ x₂…..x_i-2 , p x_i-1….yx_i+1…..x_n   

This change of ID is represented as

x₁ x₂…..x_i-1 qx_i…. x_n  |-   x₁…..x_i-2 px_i-1 yx_i+1…..x_n    

If δ(q, x_i) = (p, y, R) then change of ID is represented as

x₁ x₂…..x_i-1 qx_i…. x_n  |-   x₁ x_i-1 y p x_i+1…..x_n  

The Language Accepted by TM :

L(M) = { w | w ∈ Σ*   and  q₀w Ͱ* α1 p α2 for some p in F and  α1, α2 ∈ Γ* }

We assume that TM halts whenever the input is accepted. So TM has no next move when it enters in the final state. But if string is not accepted, it may go into infinite loop.