The states q j0 and q k0 are newstates, introduced to take care of complications
arising from the fact that in a standard Turing machine the read-write head
changes position in each move. In the macroinstruction, we want to change the
state, but leave the read-write head where it is. We let the head move right, but
put the machine into a state q j or q k0 . This indicates that a left move must be
made before entering the desired state q j or q k .
Going a step further, we can replace macroinstructions with subprograms.
Normally, a macroinstruction is replaced by actual code at each occurrence,
whereas a subprogram is a single piece of code that is invoked repeatedly
whenever needed. Subprograms are fundamental to high-level programming
languages, but they can also be used with Turing machines. To make this
plausible, let us outline briefly howa Turing machine can be used as a
subprogram that can be invoked repeatedly by another Turing machine. This
requires a newfeature: the ability to store information on the calling program's
configuration so the configuration can be recreated on return from the
subprogram. For example, say machine A in state q i invokes machine B. When B
is finished, we would like to resume program A in state q i , with the read-write
head (which may have moved during B's operation) in its original place. At other
times, A may call B from state q j , in which case control should return to this
state. To solve the control transfer problem, we must be able to pass information
from A to B and vice versa, be able to recreate A’s configuration when it recovers
control from B, and assure that the temporarily suspended computations of A are
not affected by the execution of B. To solve this, we can divide the tape into
several regions as shown in Figure 9.9.
Figure 9.9
arising from the fact that in a standard Turing machine the read-write head
changes position in each move. In the macroinstruction, we want to change the
state, but leave the read-write head where it is. We let the head move right, but
put the machine into a state q j or q k0 . This indicates that a left move must be
made before entering the desired state q j or q k .
Going a step further, we can replace macroinstructions with subprograms.
Normally, a macroinstruction is replaced by actual code at each occurrence,
whereas a subprogram is a single piece of code that is invoked repeatedly
whenever needed. Subprograms are fundamental to high-level programming
languages, but they can also be used with Turing machines. To make this
plausible, let us outline briefly howa Turing machine can be used as a
subprogram that can be invoked repeatedly by another Turing machine. This
requires a newfeature: the ability to store information on the calling program's
configuration so the configuration can be recreated on return from the
subprogram. For example, say machine A in state q i invokes machine B. When B
is finished, we would like to resume program A in state q i , with the read-write
head (which may have moved during B's operation) in its original place. At other
times, A may call B from state q j , in which case control should return to this
state. To solve the control transfer problem, we must be able to pass information
from A to B and vice versa, be able to recreate A’s configuration when it recovers
control from B, and assure that the temporarily suspended computations of A are
not affected by the execution of B. To solve this, we can divide the tape into
several regions as shown in Figure 9.9.
Figure 9.9