ABSTRACT
In the last two chapters, we have introduced several important computationalmodels, includingTuringmachines andChomsky’s hierarchyof formal grammars. In this chapter,wewill explore the limits ofmechanical computation as defined by thesemodels.We beginwith a list of fundamental problems for which automatic computational solutionwould be very useful. One of these is the universal simulationproblem: canonedesigna single algorithmthat is capableof simulatinganyalgorithm?Turing’s demonstration that the answer is yes [21] supplied the proof for Babbage’s dream of a singlemachine that could be programmed to carry out any computational task. We introduce a simple Turing machine programming language called “GOTO” in order to facilitate our own design of a universal machine. Next, we describe the schemes of primitive recursion andμ-recursion, which enable a concise, mathematical description of computable functions that is independent of any machine model. We show that the μ-recursive functions are the same as those computable on a Turing machine, and describe some computable functions, including one that solves a second problem on our list. The success in solving ends there, however. We show in the last section of this chapter that all of
the remaining problems on our list are unsolvable by Turing machines, and subject to the ChurchTuring thesis, have no mechanical or human solver at all. That is to say, there is no Turing machine or physical device, no stand-alone product of human invention, that is capable of giving the correct answer to all-or even most-instances of these problems. The implication we draw is that in order to solve some important instances of these problems, human ingenuity is needed to guide powerful computers down the paths felt most likely to yield the answers. To cite Raymond Smullyan quoting P. Rosenbloom, the results on unsolvability imply that “man can never eliminate the necessity of using his own cleverness, no matter how cleverly he tries.”
