Before A calls B, it writes the information needed by B (e.g., A’s current
state, the arguments for B) on the tape in some region T. A then passes control to
B by making a transition to the start state of B. After transfer, B will use T to find
its input. The workspace for B is separate from T and from the workspace for A,
so no interference can occur. When B is finished, it will return relevant results to
region T, where A will expect to find it. In this way, the two programs can
interact in the required fashion. Note that this is very similar to what actually
happens in a real computer when a subprogram is called.
We can nowprogram Turing machines in pseudocode, provided that we
know(in theory at least) howto translate this pseudocode into an actual Turing
machine program.
Example 9.14
Design a Turing machine that multiplies two positive integers in unary notation.
A multiplication machine can be constructed by combining the ideas we
encountered in adding and copying. Let us assume that the initial and final tape
contents are to be as indicated in Figure 9.10. The process of multiplication can
then be visualized as a repeated copying of the multiplicand y for each 1 in the
multiplier x, whereby the string y is added the appropriate number of times to the
partially computed product. The following pseudocode shows the main steps of
the process.
1. Repeat the following steps until x contains no more 1’s. Find a 1 in x and
replace it with another symbol a. Replace the leftmost 0 by 0y.
2. Replace all a’s with 1’s.
Although this pseudocode is sketchy, the idea is simple enough that there
should be no doubt that it can be done.
Figure 9.10
state, the arguments for B) on the tape in some region T. A then passes control to
B by making a transition to the start state of B. After transfer, B will use T to find
its input. The workspace for B is separate from T and from the workspace for A,
so no interference can occur. When B is finished, it will return relevant results to
region T, where A will expect to find it. In this way, the two programs can
interact in the required fashion. Note that this is very similar to what actually
happens in a real computer when a subprogram is called.
We can nowprogram Turing machines in pseudocode, provided that we
know(in theory at least) howto translate this pseudocode into an actual Turing
machine program.
Example 9.14
Design a Turing machine that multiplies two positive integers in unary notation.
A multiplication machine can be constructed by combining the ideas we
encountered in adding and copying. Let us assume that the initial and final tape
contents are to be as indicated in Figure 9.10. The process of multiplication can
then be visualized as a repeated copying of the multiplicand y for each 1 in the
multiplier x, whereby the string y is added the appropriate number of times to the
partially computed product. The following pseudocode shows the main steps of
the process.
1. Repeat the following steps until x contains no more 1’s. Find a 1 in x and
replace it with another symbol a. Replace the leftmost 0 by 0y.
2. Replace all a’s with 1’s.
Although this pseudocode is sketchy, the idea is simple enough that there
should be no doubt that it can be done.
Figure 9.10