that the input alphabet is a subset of the tape alphabet, not including the blank.
Blanks are ruled out as input for reasons that will become apparent shortly. The
transition function δ is defined as
δ : Q × Γ → Q × Γ × {L,R}.
In general,δ is a partial function on Q × Γ; its interpretation gives the principle
by which a Turing machine operates. The arguments of δ are the current state of
the control unit and the current tape symbol being read. The result is a new state
of the control unit, a new tape symbol, which replaces the old one, and a move
symbol, L or R. The move symbol indicates whether the read-write head moves
left or right one cell after the new symbol has been written on the tape.
Example 9.1
Figure 9.2 shows the situation before and after the move
δ (q 0 , a) = (q 1 , d, R).
Figure 9.2
The situation (a) before the move and (b) after the move.
We can think of a Turing machine as a rather simple computer. It has a
processing unit, which has a finite memory, and in its tape, it has a secondary
storage of unlimited capacity. The instructions that such a computer can carry
out are very limited: It can sense a symbol on its tape and use the result to decide
what to do next. The only actions the machine can perform are to rewrite the
current symbol, to change the state of the control, and to move the read-write
head. This small instruction set may seem inadequate for doing complicated
things, but this is not so. Turing machines are quite powerful in principle. The
Blanks are ruled out as input for reasons that will become apparent shortly. The
transition function δ is defined as
δ : Q × Γ → Q × Γ × {L,R}.
In general,δ is a partial function on Q × Γ; its interpretation gives the principle
by which a Turing machine operates. The arguments of δ are the current state of
the control unit and the current tape symbol being read. The result is a new state
of the control unit, a new tape symbol, which replaces the old one, and a move
symbol, L or R. The move symbol indicates whether the read-write head moves
left or right one cell after the new symbol has been written on the tape.
Example 9.1
Figure 9.2 shows the situation before and after the move
δ (q 0 , a) = (q 1 , d, R).
Figure 9.2
The situation (a) before the move and (b) after the move.
We can think of a Turing machine as a rather simple computer. It has a
processing unit, which has a finite memory, and in its tape, it has a secondary
storage of unlimited capacity. The instructions that such a computer can carry
out are very limited: It can sense a symbol on its tape and use the result to decide
what to do next. The only actions the machine can perform are to rewrite the
current symbol, to change the state of the control, and to move the read-write
head. This small instruction set may seem inadequate for doing complicated
things, but this is not so. Turing machines are quite powerful in principle. The