# ∈T is a symbol called ‘blank’
q Q
0 ∈ is the initial state
F Q
⊆ is a set of final states
As the Turing machine will have to be able to find its input, and to know
when it has processed all of that input, we require:
(a) The tape is initially “blank” (every symbol is #) except possibly
for a finite, contiguous sequence of symbols.
(b) If there are initially nonblank symbols on the tape, the tape head is
initially positioned on one of them.
This emphasises the fact that the “input” viz., the non-blank symbols on
the tape does not contain #.
4.1.3 Tran si tion Func tion, Instan ta neous Descrip tion
and Moves
The “Transition Function” for Turing Machine is given by
δ :
{ , }
Q
Q
L R
× → × ×
Γ
Γ
When the machine is in a given state (Q) and reads a given symbol (Γ) from the
tape, it replaces the symbol on the tape with some other symbol (Γ), goes to
some other state (Q), and moves the tape head one square left (L) or right (R).
An “Instantaneous Description” or “Configuration” of a Turing machine
requires.
(a) the state the Turing machine is in
(b) the contents of the tape
(c) the position of the tape head on the tape.
This is written as a string of the form
x
x q x
x
i
j m k
l
KK
KK
where the x’s are the symbols on the tape, q m is the current state, and the tape
head is on the square containing x k (the symbol immediately following q m ).
The “Move” of a Turing machine can therefore be expressed as a pair of
instantaneous descriptions, separated by a symbol “|–”.
For example, if
δ( , ) ( , , )
q b
q c R
5
8
=
then a possible move can be
abbabq babb
abbabcq abb
5
8
|–
Turing Machines
187