Next: References Up: Towards a Mathematical Science Previous: Semantics

# The Limitations of Machines And Men as Problem-Solvers

Can a man make a computer program that is as intelligent as he is? The question has two parts. First, we ask whether it is possible in principle, in view of the mathematical results on undecidability and incompleteness. The second part is a question of the state of the programming art as it concerns artificial intelligence. Even if the answer to the first question is ``no'', one can still try to go as far as possible in solving problems by machine.

My guess is that there is no such limitation in principle. However, a complete discussion involves the deeper parts of recursive function theory, and the necessary mathematics has not all been developed.

Consider the problem of deciding whether a sentence of the lower predicate calculus is a theorem. Many problems of actual mathematical or scientific interest can be formulated in this form, and this problem has been proved equivalent to many other problems including problem of determining whether a program on a computer with unlimited memory will ever stop. According to Post, this is equivalent to deciding whether an integer is a member of what Post calls a creative set. It was proved by Myhill that all creative sets are equivalent in a quite strong sense, so that there is really only one class of problems at this level of unsolvability.

Concerning this problem the following facts are known:

1) There is a procedure which will do the following: If the number is in the creative set, the procedure will say ``yes'', and if the number is not in the creative set the procedure will not say ``yes'', it may say ``no'' or it may run on indefinitely.

2) There is no procedure which will always say ``yes'' when the answer is ``yes'', and will always say ``no'' when the answer is ``no'' If a procedure has property (1) it must sometimes run on indefinitely. Thus there is no procedure which can always decide definitely whether a number is a member of a creative set, or equivalently, whether a sentence of the lower predicate calculus is a theorem, or whether an ALGOL program with given input will ever stop. This is the sense in which these problems are unsolvable.

3) Now we come to Post's surprising result. We might try to do as well as possible. Namely, we can try to find a procedure that always says ``yes'' when the answer is ``yes", and never says ``yes" when the answer is ``no'', and which says ``no" for as large a class of the negative cases as possible, thus narrowing down the set of cases where the procedure goes on indefinitely as much as we can. Post showed that one cannot even do as well as possible. Namely, Post gave a procedure which, when given any other partial decision procedure, would give a better one. The better procedure decides all the cases the first procedure decided, and an infinite class of new ones. At first sight this seems to suggest that Emil Post was more intelligent than any possible machine, although Post himself modestly refrained from drawing this conclusion. Whatever program you propose, Post can do better. However, this is unfair to the programs. Namely, Post's improvement procedure is itself mechanical and can be carried out by machine, so that the machine can improve its own procedure or can even improve Post, if given a description of Post's own methods of trying to decide sentences of the lower predicate calculus. It is like a contest to see who can name the largest number. The fact that I can add one to any number you give, does not prove that I am better than you are.

4) However, the situation is more complicated than this. Obviously, the improvement process may be carried out any finite number of times and a little thought shows that the process can be carried out an infinite number of times. Namely, let p be the original procedure, and let Post's improvement procedure be called P, then represents the original procedure improved n times. We can define as a procedure that applies p for a while, then for a while, then p again, then , then , then p, then , then , then , etc. This procedure will decide any problem that any will decide, and so may justifiably be called . However, is itself subject to Post's original improvement process and the result may be called . How far can this go? The answer is technical. Namely, given any recursive transfinite ordinal , one can define . A recursive ordinal is a recursive ordering of the integers that is a well-ordering in the sense that any subset of the integers has a least member in the sense of the ordering. Thus, we have a contest in trying to name the largest recursive ordinal. Here we seem to be stuck, because the limit of the recursive ordinals is not recursive. However, this does not exclude the possibility that there is a different improvement process Q, such that Qp is better than for any recursive ordinal .

5) There is yet another complication. Suppose someone names what he claims is a large recursive ordinal. We, or our program, can name a larger one by adding one, but how do we know that the procedure that he claims is a recursive well-ordering, really is? He says he has proved it in some system of arithmetic. In the first place we may not be confident that his system of arithmetic is correct or even consistent. But even if the system is correct, by Gödel's theorem it is incomplete. In particular, there are recursive ordinals that cannot be proved to be so in that system. Rosenbloom, in his book ``Elements of Mathematical Logic" drew the conclusion that man was in principle superior to machines because, given any formal system of arithmetic, he could give a stronger system containing true and provable sentences that could not be proved in the original system. What Rosenbloom missed, presumably for sentimental reasons, is that the improvement procedure is itself mechanical, and subject to iteration through the recursive ordinals, so that we are back in the large ordinal race. Again we face the complication of proving that our large ordinals are really ordinals.

6) These considerations have little practical significance in their present form. Namely, the original improvement process is such that the improved process is likely to be too slow to get results in a reasonable time, whether carried out by man or by machine. It may be possible, however, to put this hierarchy in some usable form.

In conclusion, let me re-assert that the question of whether there are limitations in principle of what problems man can make machines solve for him as compared to his own ability to solve problems, really is a technical question in recursive function theory.

Next: References Up: Towards a Mathematical Science Previous: Semantics

John McCarthy
Tue May 14 13:32:03 PDT 1996