4.1.4 Pro gramming a Turing Machine
As we have the “productions” as the control theme of a grammar, the
“transitions” are the central theme of a Turing machine. These transitions are
given as a table or list of S-tuples, where each tuple has the form
(cur rent state, sym bol read, sym bol writ ten, direc tion, next state)
Creating such a list is called “programming” a Turing machine.
A Turing machine is often defined to start with the read head positioned
over the first (leftmost) input symbol. This is not really necessary, because if
the Turing machine starts anywhere on the nonblank portion of the tape, it is
simple to get to the first input symbol.
For the input alphabet Σ = { , }
a b , the following program fragment does the
trick, then goes to state q 1 .
( , , , , )
( , , , , )
( , # , # , , )
q a a L q
q b b L q
q
R q
0
0
0
0
0
1
4.1.5 Turing Machines as Accep tors
A Turing machine halts when it no longer has available moves. If it halts in a
final state, it accepts its input, otherwise it rejects its input.
A Turing machine T
Q
q
F
= ( , , , , , # , )
Σ Γ δ 0
accepts a language L(M),
where
L M
w
q w x q x
q
F x x
i f j
f
i
j
( ) (
:
|–
, ,
),
*
*
= ∈
∈
∈
+
Σ
Γ
0
for some
with the assumption that the Turing machine starts with its tape head
positioned on the leftmost symbol.
A Turing Machine accepts its input if it halts in a final state. There are two
ways this could fail to happen:
(a) The Turing machine could halt in a nonfinal state or
(b) The Turing machine could never stop i.e., it enters an “infinite
loop”.
4.1.6 How to Recognize a Language
This machine will match strings of the form
{
:
}
a b n
n n
≥ 0
q 1 is the only “final state”.
q 4 (which has no available moves at all) serves as an “error state”.
188
Theory of Automata, Formal Languages and Computation