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.

Tue May 14 13:32:03 PDT 1996