The preceding discussion not only shows how a Turing machine can be
constructed from simpler parts, but also illustrates a negative aspect of working
with such low-level automata. While it takes very little imagination or ingenuity
to translate a block diagram or pseudocode into the corresponding Turing
machine program, actually doing it is time-consuming, error-prone, and adds
little to our understanding. The instruction set of a Turing machine is so
restricted that any argument, solution, or proof for a nontrivial problem is quite
tedious.
We nowface a dilemma: We want to claim that Turing machines can perform
not only the simple operations for which we have provided explicit programs,
but also more complex processes as well, describable by block diagrams or
pseudocode. To defend such claims against challenge, we should showthe
relevant programs explicitly. But doing so is unpleasant and distracting, and
ought to be avoided if possible. Somehow, we would like to find a way of
carrying out a reasonably rigorous discussion of Turing machines without having
to write lengthy, low-level code. There is unfortunately no completely
satisfactory way of getting out of the predicament; the best we can do is to reach
a reasonable compromise. To see how we might achieve such a compromise, we
turn to a somewhat philosophical issue.
We can drawsome simple conclusions from the examples in the previous
section. The first is that Turing machines appear to be more powerful than
pushdown automata (for a comment on this, see Exercise 2 at the end of this
section). In Example 9.8, we sketched the construction of a Turing machine for a
language that is not context-free and for which, consequently, no pushdown
automaton exists. Examples 9.9, 9.10, and 9.11 show that Turing machines can
do some simple arithmetic operations, perform string manipulations, and make
some simple comparisons. The discussion also illustrates how primitive
operations can be combined to solve more complex problems, how several
Turing machines can be composed, and how one program can act as a
subprogram for another. Since very complex operations can be built this way, we
might suspect that a Turing machine begins to approach a typical computer in
power.
Suppose we were to make the conjecture that, in some sense, Turing
machines are equal in power to a typical digital computer? How could we defend
or refute such a hypothesis? To defend it, we could take a sequence of
increasingly more difficult problems and show how they are solved by some
Turing machine. We might also take the machine language instruction set of a
specific computer and design a Turing machine that can perform all the
constructed from simpler parts, but also illustrates a negative aspect of working
with such low-level automata. While it takes very little imagination or ingenuity
to translate a block diagram or pseudocode into the corresponding Turing
machine program, actually doing it is time-consuming, error-prone, and adds
little to our understanding. The instruction set of a Turing machine is so
restricted that any argument, solution, or proof for a nontrivial problem is quite
tedious.
We nowface a dilemma: We want to claim that Turing machines can perform
not only the simple operations for which we have provided explicit programs,
but also more complex processes as well, describable by block diagrams or
pseudocode. To defend such claims against challenge, we should showthe
relevant programs explicitly. But doing so is unpleasant and distracting, and
ought to be avoided if possible. Somehow, we would like to find a way of
carrying out a reasonably rigorous discussion of Turing machines without having
to write lengthy, low-level code. There is unfortunately no completely
satisfactory way of getting out of the predicament; the best we can do is to reach
a reasonable compromise. To see how we might achieve such a compromise, we
turn to a somewhat philosophical issue.
We can drawsome simple conclusions from the examples in the previous
section. The first is that Turing machines appear to be more powerful than
pushdown automata (for a comment on this, see Exercise 2 at the end of this
section). In Example 9.8, we sketched the construction of a Turing machine for a
language that is not context-free and for which, consequently, no pushdown
automaton exists. Examples 9.9, 9.10, and 9.11 show that Turing machines can
do some simple arithmetic operations, perform string manipulations, and make
some simple comparisons. The discussion also illustrates how primitive
operations can be combined to solve more complex problems, how several
Turing machines can be composed, and how one program can act as a
subprogram for another. Since very complex operations can be built this way, we
might suspect that a Turing machine begins to approach a typical computer in
power.
Suppose we were to make the conjecture that, in some sense, Turing
machines are equal in power to a typical digital computer? How could we defend
or refute such a hypothesis? To defend it, we could take a sequence of
increasingly more difficult problems and show how they are solved by some
Turing machine. We might also take the machine language instruction set of a
specific computer and design a Turing machine that can perform all the