Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

INTRODUCTION TO TURNING MACHINE 335

A cell contains no input symbol and no tape symbol certainly contains the ‘blank sym-

bol’. It is used to distinguish between the input symbols and tape symbols.

The tape is pointed by the tape head such that at any moment tape is head centered on

one of the cell of the tape. The movement of the tape head may consists of following:

1. It moves one cell left (unless it is not on the left most cell)/right at a time.


2. It replaces the current symbol either by a tape symbol or through blank symbol.


3. And changing the state.

12.2.1Abstract View of a TM

a a b a c c B B B B ..........

M

T

q 0

b a b a c c B ..........

M

p

¥

Þ

()a ()b
Fig. 12.1
Assume that at time t = 0 Machine M is in state q 0 (initial state) and its tape head
pointing to its left most cell. Tape cells contain the string of input symbols (form over Σ) and
the remaining cells hold the blank symbol/s that is shown by B’s. Machine has a read/write
tape head T that scans one cell at a time. Assume that after reading the symbol ‘a’ machine
reaches to state p and simultaneously tape head replaces the input symbol by another tape
symbol let it be ‘b’ and move to right. Now tape head pointed to the second cell containing the
input symbol ‘a’. In this way M scans all cells that contain the input symbol and left the tape
symbols that will be the possible form of output generated by the Turing Machine M. The
abstract view of turing machine is shown in Fig. 12.1(a) & (b).

12.2.2 Definition of a TM

Once we know the characteristics of the Turing Machine, we can easily define it in the

forms of set of following tuples,

• A finite set of states (Q)


• A finite set of input symbols (Σ)


• A finite set of tape symbols (Γ); where Σ ⊂ Γ


• Blank symbol (B); where B Σ Γ but B ∉ Σ


• A starting state (q 0 ); where q 0 ∈ Q


• Transition function ∂, where ∂ is: (partial mapping of)
  δ : Q ∗ {Γ ∪ Σ} → Q ∗ {Γ ∪ Σ} ∗ (L, R)
  That is the arguments of ∂ are a state q (∈ Q) and a tape/input symbol ‘a’ (∈ {Γ ∪ Σ}) and
  returns to the next state p (∈ Q), replacing another symbol ‘b’ (∪ {Γ ∪ Σ}) and moves either left
  or right, i.e.
  δ (q, a) = (p, b, R); here we assume tape head moves right.


• The set of final state/s (F); where F ⊆ Q
  So, above 7-tuples describe the TM M as,
  M = (Q, Σ, Γ, B, q 0 , δ, F)