H
Chapter 12
Limits of Algorithmic Computation
aving talked about what Turing machines can do, we now look at
what they cannot do. Although Turing's thesis leads us to believe that
there are few limitations to the power of a Turing machine, we have
claimed on several occasions that there could not exist any algorithms
for the solution of certain problems. Now we make more explicit
what we mean by this claim. Some of the results came about quite simply;if a
language is nonrecursive, then by definition there is no membership algorithm
for it. If this were all there was to this issue, it would not be very interesting;
nonrecursive languages have little practical value. But the problem goes deeper.
For example, we have stated (but not yet proved) that there exists no algorithm
to determine whether a context-free grammar is unambiguous. This question is
clearly of practical significance in the study of programming languages.
We first define the concepts of decidability and computability to pin down
what we mean when we say that something cannot be done by a Turing machine.
We then look at several classical problems of this type, among them the wellknown halting problem for Turing machines. From this follow a number of
related problems for Turing machines and recursively enumerable languages.
After this, we look at some questions relating to context-free languages. Here we
find quite a few important problems for which, unfortunately, there are no
algorithms.
12.1 Some Problems That Cannot Be Solved by
Turing Machines
The argument that the power of mechanical computations is limited is not
surprising. Intuitively we know that many vague and speculative questions
require special insight and reasoning well beyond the capacity of any computer
Chapter 12
Limits of Algorithmic Computation
aving talked about what Turing machines can do, we now look at
what they cannot do. Although Turing's thesis leads us to believe that
there are few limitations to the power of a Turing machine, we have
claimed on several occasions that there could not exist any algorithms
for the solution of certain problems. Now we make more explicit
what we mean by this claim. Some of the results came about quite simply;if a
language is nonrecursive, then by definition there is no membership algorithm
for it. If this were all there was to this issue, it would not be very interesting;
nonrecursive languages have little practical value. But the problem goes deeper.
For example, we have stated (but not yet proved) that there exists no algorithm
to determine whether a context-free grammar is unambiguous. This question is
clearly of practical significance in the study of programming languages.
We first define the concepts of decidability and computability to pin down
what we mean when we say that something cannot be done by a Turing machine.
We then look at several classical problems of this type, among them the wellknown halting problem for Turing machines. From this follow a number of
related problems for Turing machines and recursively enumerable languages.
After this, we look at some questions relating to context-free languages. Here we
find quite a few important problems for which, unfortunately, there are no
algorithms.
12.1 Some Problems That Cannot Be Solved by
Turing Machines
The argument that the power of mechanical computations is limited is not
surprising. Intuitively we know that many vague and speculative questions
require special insight and reasoning well beyond the capacity of any computer