…” However, to construct explicitly an algorithm for even relatively simple
problems is a very lengthy undertaking. To avoid such unpleasant prospects, we
can appeal to Turing's thesis and claim that anything we can do on any computer
can also be done on a Turing machine. Consequently, we could substitute “C
program” for “Turing machine” in Definition 9.5. This would ease the burden of
exhibiting algorithms considerably. Actually, as we have already done, we will
go one step further and accept verbal descriptions or block diagrams as
algorithms on the assumption that we could write a Turing machine program for
them if we were challenged to do so. This greatly simplifies the discussion, but it
obviously leaves us open to criticism. While “C program” is well defined, “clear
verbal description” is not, and we are in danger of claiming the existence of
nonexistent algorithms. But this danger is more than offset by the facts that we
can keep the discussion simple and intuitively clear and that we can give concise
descriptions for some rather complex processes. The reader who has any doubts
about the validity of these claims can dispel them by writing a suitable program
in some programming language.
EXERCISES
** 1. Consider the set of machine language instructions for a computer of your
choice. Sketch how the various instructions in this set could be carried out by
a Turing machine.
2. In the above discussion, we stated at one point that Turing machines appear to
be more powerful than pushdown automata. Since the tape of a Turing
machine can always be made to behave like a stack, it would seem that we
can actually claim that a Turing machine is more powerful. What important
factor is not taken into account in this argument?
** 3. There are a number of enjoyable articles on Turing machines in the popular
literature. A good one is a paper in Scientific American, May 1984, by J. E.
Hopcroft, titled “Turing Machines”. This paper talks about the ideas we have
introduced here and also gives some of the historical context in which the
work of Turing and others was done. Get a copy of this article and read it,
then write a brief review of it.
problems is a very lengthy undertaking. To avoid such unpleasant prospects, we
can appeal to Turing's thesis and claim that anything we can do on any computer
can also be done on a Turing machine. Consequently, we could substitute “C
program” for “Turing machine” in Definition 9.5. This would ease the burden of
exhibiting algorithms considerably. Actually, as we have already done, we will
go one step further and accept verbal descriptions or block diagrams as
algorithms on the assumption that we could write a Turing machine program for
them if we were challenged to do so. This greatly simplifies the discussion, but it
obviously leaves us open to criticism. While “C program” is well defined, “clear
verbal description” is not, and we are in danger of claiming the existence of
nonexistent algorithms. But this danger is more than offset by the facts that we
can keep the discussion simple and intuitively clear and that we can give concise
descriptions for some rather complex processes. The reader who has any doubts
about the validity of these claims can dispel them by writing a suitable program
in some programming language.
EXERCISES
** 1. Consider the set of machine language instructions for a computer of your
choice. Sketch how the various instructions in this set could be carried out by
a Turing machine.
2. In the above discussion, we stated at one point that Turing machines appear to
be more powerful than pushdown automata. Since the tape of a Turing
machine can always be made to behave like a stack, it would seem that we
can actually claim that a Turing machine is more powerful. What important
factor is not taken into account in this argument?
** 3. There are a number of enjoyable articles on Turing machines in the popular
literature. A good one is a paper in Scientific American, May 1984, by J. E.
Hopcroft, titled “Turing Machines”. This paper talks about the ideas we have
introduced here and also gives some of the historical context in which the
work of Turing and others was done. Get a copy of this article and read it,
then write a brief review of it.