Before introducing other models, we make one remark on the standard
Turing machine. It is implicit in Definition 9.1 that each tape symbol can be a
composite of characters rather than just a single one. This can be made more
explicit by drawing an expanded version of Figure 9.1 (Figure 10.1), in which
the tape symbols are triplets from some simpler alphabet.
In the picture, we have divided each cell of the tape into three parts, called
tracks, each containing one member of the triplet. Based on this visualization,
such an automaton is sometimes called a Turing machine with multiple tracks,
but such a view in no way extends Definition 9.1, since all we need to do is
make Γ an alphabet in which each symbol is composed of several parts.
However, other Turing machine models involve a change of definition, so the
equivalence with the standard machine has to be demonstrated. Here we look at
two such models, which are sometimes used as the standard definition. Some
variants that are less common are explored in the exercises at the end of this
section.
Turing Machines with Semi-Infinite Tape
Many authors do not consider the model in Figure 9.1 as standard, but use one
with a tape that is unbounded only in one direction. We can visualize this as a
tape that has a left boundary (Figure 10.2). This Turing machine is otherwise
identical to our standard model, except that no left move is permitted when the
read-write head is at the boundary.
Figure 10.2
Figure 10.3
Turing machine. It is implicit in Definition 9.1 that each tape symbol can be a
composite of characters rather than just a single one. This can be made more
explicit by drawing an expanded version of Figure 9.1 (Figure 10.1), in which
the tape symbols are triplets from some simpler alphabet.
In the picture, we have divided each cell of the tape into three parts, called
tracks, each containing one member of the triplet. Based on this visualization,
such an automaton is sometimes called a Turing machine with multiple tracks,
but such a view in no way extends Definition 9.1, since all we need to do is
make Γ an alphabet in which each symbol is composed of several parts.
However, other Turing machine models involve a change of definition, so the
equivalence with the standard machine has to be demonstrated. Here we look at
two such models, which are sometimes used as the standard definition. Some
variants that are less common are explored in the exercises at the end of this
section.
Turing Machines with Semi-Infinite Tape
Many authors do not consider the model in Figure 9.1 as standard, but use one
with a tape that is unbounded only in one direction. We can visualize this as a
tape that has a left boundary (Figure 10.2). This Turing machine is otherwise
identical to our standard model, except that no left move is permitted when the
read-write head is at the boundary.
Figure 10.2
Figure 10.3