For the sake of discussion, assume that x and y are positive integers in unary
representation. The value zero will be represented by 0, with the rest of the tape
blank.
The computation of f (x, y) can be visualized at a high level by means of the
diagram in Figure 9.8. The diagram shows that we first use a comparing
machine, like that in Example 9.11, to determine whether or not x ≥ y. If so, the
comparer sends a start signal to the adder, which then computes x + y. If not, an
erasing program is started that changes every 1 to a blank.
In subsequent discussions, we will often use such high-level, black-diagram
representations of Turing machines. It is certainly quicker and clearer than the
corresponding extensive set of δ’s. Before we accept this high-level view, we
must justify it. What, for example, is meant by saying that the comparer sends a
start signal to the adder? There is nothing in Definition 9.1 that offers that
possibility. Nevertheless, it can be done in a straightforward way.
Figure 9.8
The program for the comparer C is written as suggested in Example 9.11,
using a Turing machine having states indexed with C. For the adder, we use the
idea in Example 9.9, with states indexed with A. For the eraser E, we construct a
Turing machine having states indexed with E. The computations to be done by C
are
and
If we take q A,0 and q E,0 as the initial states of A and E, respectively, we see that C
starts either A or E.
The computations performed by the adder will be
representation. The value zero will be represented by 0, with the rest of the tape
blank.
The computation of f (x, y) can be visualized at a high level by means of the
diagram in Figure 9.8. The diagram shows that we first use a comparing
machine, like that in Example 9.11, to determine whether or not x ≥ y. If so, the
comparer sends a start signal to the adder, which then computes x + y. If not, an
erasing program is started that changes every 1 to a blank.
In subsequent discussions, we will often use such high-level, black-diagram
representations of Turing machines. It is certainly quicker and clearer than the
corresponding extensive set of δ’s. Before we accept this high-level view, we
must justify it. What, for example, is meant by saying that the comparer sends a
start signal to the adder? There is nothing in Definition 9.1 that offers that
possibility. Nevertheless, it can be done in a straightforward way.
Figure 9.8
The program for the comparer C is written as suggested in Example 9.11,
using a Turing machine having states indexed with C. For the adder, we use the
idea in Example 9.9, with states indexed with A. For the eraser E, we construct a
Turing machine having states indexed with E. The computations to be done by C
are
and
If we take q A,0 and q E,0 as the initial states of A and E, respectively, we see that C
starts either A or E.
The computations performed by the adder will be