δ (q i , a) = (q j ,b, L or R),
then a and b must be different. Does this limitation reduce the power of the
automaton?
10. Consider a version of the standard Turing machine in which transitions can
depend not only on the cell directly under the read-write head, but also on
the cells to the immediate right and left. Make a formal definition of such a
machine, then sketch its simulation by a standard Turing machine.
11. Consider a Turing machine with a different decision process in which
transitions are made if the current tape symbol is not one of a specified set.
For example,
δ (q i , {a, b}) = (q j , c, R)
will allow the indicated move if the current tape symbol is neither a nor b.
Formalize this concept and show that this modification is equivalent to a
standard Turing machine.
10.2 Turing Machines with More Complex Storage
The storage device of a standard Turing machine is so simple that one might
think it possible to gain power by using more complicated storage devices. But
this is not the case, as we now illustrate with two examples.
Multitape Turing Machines
A multitape Turing machine is a Turing machine with several tapes, each with its
own independently controlled read-write head (Figure 10.8).
The formal definition of a multitape Turing machine goes beyond Definition
9.1, since it requires a modified transition function. Typically, we define an ntape machine by M = (Q, Σ, Γ, δ, q 0 , F), where Q,Σ, Y,q o ,F are as in Definition
9.1, but where
δ : Q × Γ n → Q × Γ n × {L, R} n
then a and b must be different. Does this limitation reduce the power of the
automaton?
10. Consider a version of the standard Turing machine in which transitions can
depend not only on the cell directly under the read-write head, but also on
the cells to the immediate right and left. Make a formal definition of such a
machine, then sketch its simulation by a standard Turing machine.
11. Consider a Turing machine with a different decision process in which
transitions are made if the current tape symbol is not one of a specified set.
For example,
δ (q i , {a, b}) = (q j , c, R)
will allow the indicated move if the current tape symbol is neither a nor b.
Formalize this concept and show that this modification is equivalent to a
standard Turing machine.
10.2 Turing Machines with More Complex Storage
The storage device of a standard Turing machine is so simple that one might
think it possible to gain power by using more complicated storage devices. But
this is not the case, as we now illustrate with two examples.
Multitape Turing Machines
A multitape Turing machine is a Turing machine with several tapes, each with its
own independently controlled read-write head (Figure 10.8).
The formal definition of a multitape Turing machine goes beyond Definition
9.1, since it requires a modified transition function. Typically, we define an ntape machine by M = (Q, Σ, Γ, δ, q 0 , F), where Q,Σ, Y,q o ,F are as in Definition
9.1, but where
δ : Q × Γ n → Q × Γ n × {L, R} n