one class, there is a machine in the second class capable of simulating it, and
vice versa.
Turing Machines with a Stay-Option
In our definition of a standard Turing machine, the read-write head must move
either to the right or to the left. Sometimes it is convenient to provide a third
option, to have the read-write head stay in place after rewriting the cell content.
Thus, we can define a Turing machine with a stay-option by replacing δ in
Definition 9.1 by with the interpretation that S signifies no movement of the
read-write head. This option does not extend the power of the automaton.
δ : Q × Γ→ Q × Γ ×{L, R, S}
Theorem 10.1
The class of Turing machines with a stay-option is equivalent to the class of
standard Turing machines.
Proof: Since a Turing machine with a stay-option is clearly an extension of the
standard model, it is obvious that any standard Turing machine can be simulated
by one with a stay-option.
To show the converse, let M = (Q, Σ,Γ,δ, q 0 , ,F) be a Turing machine with a
stay-option to be simulated by a standard Turing machine
. For each move of M, the simulating machine
does the following. If the move of M does not involve the stay-option, the
simulating machine performs one move, essentially identical to the move to be
simulated. If S is involved in the move of M, then will make two moves: The
first rewrites the symbol and moves the read-write head right; the second moves
the read-write head left, leaving the tape contents unaltered. The simulating
machine can be constructed from M by defining , as follows: For each
transition
δ(q i ,a) = (q j , b, L or R),
we put into