EXERCISES
1. Give a formal definition of a Turing machine with a semi-infinite tape. Then
prove that the class of Turing machines with semi-infinite tape is equivalent
to the class of standard Turing machines.
2. Give a formal definition of an offline Turing machine.
3. Give convincing arguments that any language accepted by an offline Turing
machine is also accepted by some standard machine.
4. Consider a Turing machine that, on any particular move, can either change
the tape symbol or move the read-write head, but not both.
(a) Give a formal definition of such a machine.
(b) Show that the class of such machines is equivalent to the class of
standard Turing machines.
5. Consider a model of a Turing machine in which each move permits the readwrite head to travel more than one cell to the left or right, the distance and
direction of travel being one of the arguments of δ. Give a precise definition
of such an automaton and sketch a simulation of it by a standard Turing
machine.
6. A nonerasing Turing machine is one that cannot change a nonblank symbol to
a blank. This can be achieved by the restriction that if
δ (q i , a) = (q j , , L or R),
then a must be . Show that no generality is lost by making such a
restriction.
7. Consider a Turing machine that cannot write blanks; that is, for all δ (q i , a) =
(q j , b, L or R), b must be in Γ-{ }. Show how such a machine can simulate a
standard Turing machine.
8. Suppose we make the requirement that a Turing machine can halt only in a
final state, that is, we ask that δ (q, a) be defined for all pairs (q, a) with a ∈
Γ and q ∉ F. Does this restrict the power of the Turing machine?
9. Suppose we make the restriction that a Turing machine must always write a
symbol different from the one it reads, that is, if
1. Give a formal definition of a Turing machine with a semi-infinite tape. Then
prove that the class of Turing machines with semi-infinite tape is equivalent
to the class of standard Turing machines.
2. Give a formal definition of an offline Turing machine.
3. Give convincing arguments that any language accepted by an offline Turing
machine is also accepted by some standard machine.
4. Consider a Turing machine that, on any particular move, can either change
the tape symbol or move the read-write head, but not both.
(a) Give a formal definition of such a machine.
(b) Show that the class of such machines is equivalent to the class of
standard Turing machines.
5. Consider a model of a Turing machine in which each move permits the readwrite head to travel more than one cell to the left or right, the distance and
direction of travel being one of the arguments of δ. Give a precise definition
of such an automaton and sketch a simulation of it by a standard Turing
machine.
6. A nonerasing Turing machine is one that cannot change a nonblank symbol to
a blank. This can be achieved by the restriction that if
δ (q i , a) = (q j , , L or R),
then a must be . Show that no generality is lost by making such a
restriction.
7. Consider a Turing machine that cannot write blanks; that is, for all δ (q i , a) =
(q j , b, L or R), b must be in Γ-{ }. Show how such a machine can simulate a
standard Turing machine.
8. Suppose we make the requirement that a Turing machine can halt only in a
final state, that is, we ask that δ (q, a) be defined for all pairs (q, a) with a ∈
Γ and q ∉ F. Does this restrict the power of the Turing machine?
9. Suppose we make the restriction that a Turing machine must always write a
symbol different from the one it reads, that is, if