Godel’s Theorem: Beyond Computation

In my first article on AI, The Robotic Bull in the China Shop, I used John Searle’s Chinese Room argument to argue against the conceptual coherency of Strong AI. I feel that it was not enough. True, some people may have been convinced by the article and the argument, but Strong AI is an obstinately defended position, a heavily fortified philosophical stronghold. And a battalion comprised of a solitary argument does not a successful coup make. In order to usurp and dethrone Strong AI, more logical soldiers are necessary. (I promise I’m finished with the military analogies.) In this article, I will use Godel’s theorem as further evidence that Strong AI is an untenable position and must be rejected.

Godel’s theorem proves that human mathematicians rely on a kind of understanding which exists outside of, over and beyond, the kind of knowledge and understanding yielded by the rules of strict computational logic, the only rules allowed by Strong AI. When it comes to comprehending mathematical truths, there is simply more involved, more going on, more complexity, more mystery. In order to understand the truth of this theorem, we need to establish some parameters and delve into formal logic. It may be necessary to read through the argument presented below a few times, but the effort is worthwhile as Godel’s theorem is profoundly important when discussing matters of AI.

What we are dealing with, in purely theoretical and logical terms, are functions or computations. The kinds of programs and algorithms modern computers use in running everyday operations. And the kind of programs and algorithms that some erroneously assert will eventually lead to the development of AI, if only the programs and algorithms are sufficiently sophisticated. What Godel’s theorem shows is that no amount of sophistication is sufficient.

Firstly, “we need to consider a computation that depends on-or acts upon-a natural number” (72). Let us call such a computation C(n). “Regard n as merely providing the ‘data’ for the action of some programmed computer. What we are interested in is whether or not this computer action ever stops, for each choice of n” (72). Some clarification may be in order concerning what is meant by a computation depending on a natural number. Consider the following example:

We have computation (G), whose action depends upon the parameter: find an odd number that is the sum of two even numbers. We need not waste our time wondering if (G) will ever stop, that is if it will ever find a natural number which satisfies the parameter. There is no natural number that is an odd number that is also the sum of two even numbers. (G) will forever compute.

Now, “suppose that we have some computational procedure which, when it terminates, provides us with a demonstration that a computation such as C(n) actually does not stop” (73). “In order for A to apply to computations generally, we shall need a way of coding all the different computations C(n) so that A can use this coding for its actions” (74). We do this by using a separate computation for each natural number, written as C(0), C(1), C(2), C(3), C(4)…C(q), where C(q) is the qth computation. When one of these computations is applied to a particular natural number, we will write C0(n), C1(n), C2(n), C3(n), C4(n)…Cq(n).

“The procedure A can now be thought of as a particular computation that, when presented with a pair of numbers q, n, tries to ascertain that the computation Cq(n) will never ultimately halt. Thus, when the computation A terminates, we shall have a demonstration that Cq(ndoes not halt” (74). When considering the procedure A, we are imagining a formalization of all the procedures that are available to human mathematicians for determining if computations will halt or continue indefinitely. “Being dependent upon two numbers q and n, the computation that A performs can be written A(q, n)” (74), and we then derive:

(H): If A(q, n) stops, then Cq(n) does not stop.

What follows may seem like a bit of logical legerdemain, but I assure you everything that follows is perfectly valid and within universally accepted boundaries. Let us consider the particular instances when q is equal to n, that is, when they are the same natural number. We now produce:

(I): If A(n, n) stops, then Cn(n) does not stop.

Now that A(n, n) depends upon just one natural number, we know that it must be one of the computations C0, C1, C2, C3… It is perfectly logical to suppose that the computation is in fact Ck, since this computation will eventually arise. Now we have:

(J)A(n, n) = Ck(k)

Remember when we applied the case of qand derived statement (I)? We can make a similar move with statement (J) and apply the particular case where n = k, thereby arriving at:

(K): A(k, k) = Ck(k)

Statement (I) now reads:

If A(k, k) stops, then Ck(k) does not stop.

However, (K) tells us that A(k, k) = Ck(k), so we can apply the rule of substitution and finally conclude with:

(M): If Ck(k) stops, then Ck(k) does not stop.

We can now deduce that the computation Ck(k) does not stop. After all, according to (M), if it did then it does not. But A(k, k) cannot stop either, because we know from (K) that A(k, k) = Ck(k). Therefore, it is impossible for procedure A to determine that Ck(k) does not stop even though it is obvious that it does not. And if we know that A is sound, then we know that Ck(k) does not stop. Therefore, we know something that A is unable to ascertain.

What does this very complex and intricate theorem really prove, then? It shows us that “no knowably sound set of computational rules…can ever suffice for ascertaining that computations do not stop, since there are some non-stopping computations…that must elude these rules” (75). Since we can construct a computation that we can see, by carefully following the trail of logic bread crumbs, does not ever stop, and at the same time see that this knowledge forever eludes any set of strict computational rules, we can therefore conclude unequivocally that “human mathematicians are not using…knowably sound algorithm(s) in order to ascertain mathematical truth” (76).

The truth of Godel’s theorem asserts that no set of algorithms or computational procedures could ever categorically encapsulate human understanding, or, for that matter, human intelligence. Therefore, since Strong AI relies solely on algorithms and computational procedures to recreate or simulate intelligence, it will categorically fail. Period. Human consciousness, awareness, and intelligence, cannot be attributed to simple computational procedures, because there is some aspect of consciousness, awareness, and intelligence, as elucidated by Godel’s theorem, that lies outside of these strict boundaries. To take such a posturing is more than ugly reductionism, it is to imprecate and demean the human condition. It is unpardonable prevarication, and moreover, conceptually incoherent. Period.



Work Cited

Penrose, Roger. Shadows of the Mind. New York: Oxford University Press, 1994. pgs 72-76.




Latest Articles by gridteam (see all)

You Might Also Like