Gödel, Penrose and Artificial Intelligence -- Simplified

The mathematician Kurt Gödel became famous for his incompleteness theorems, published in 1931. Gödel proved a theorem which implied that, given any consistent formal system of axioms, there exists a true statement which cannot be proved using those axioms. This statement is called a Gödel sentence for that formal system.

Surprisingly, some people -- notably, the mathematician and physicist Roger Penrose (in his books, The Emperor's New Mind and Shadows of the Mind) -- have used this to claim that human intelligence cannot be an algorithm.

Proof: How does this claim work? Loosely speaking, algorithms correspond to formal systems. Suppose, then, that we have a mathematician Mr. A, who has studied Gödel's theorems. Assume that Mr. A, a human, is an algorithm -- and hence a formal system. Find a Gödel sentence for the formal system consisting of Mr. A. Now, Mr. A has studied Gödel's theorems, so he knows that a Gödel sentence is true and can prove it, since this proof is precisely what he studied. Thus the sentence is provable using Mr. A's formal system. But this is a contradiction since a Gödel sentence, by definition, cannot be proved using the axioms of Mr. A's formal system. Thus, Mr. A can do something -- prove a Gödel sentence -- which no formal system should be able to do. Thus the statement that Mr. A is a formal system is false.

Objection 1: Proponents of AI have criticized this argument. The most common criticism is the following: look at Gödel's theorem above again. It holds only for consistent formal systems. Thus, Mr. A would have to be a consistent formal system for Penrose's argument to make sense. But who says humans are consistent? Even mathematicians like Mr. A may contradict themselves sometimes, and so are not necessarily consistent. You would first have to prove that humans are consistent for this argument to work. (Indeed, Penrose does spend considerable effort trying to prove just this, but it has not convinced his detractors.)

Objection 2: I think that there is a stronger reason why Penrose's argument fails. The problem is in the sentence "Mr. A has studied Gödel's theorems, so he knows that a Gödel sentence is true and can prove it", taken from my simplified version of Penrose's proof above. This statement has two interpretations. It is true -- only when interpreted correctly. Its two interpretations are so similar that we naturally confuse them. Here are the interpretations:

1. If Mr. A is given a sentence and is told that it is a Gödel sentence, then he knows that it is true
2. If Mr. A is given any sentence, he can recognize whether it is a Gödel sentence, and if it is he knows that it is true.

The first interpretation is true. The second is not necessarily true -- Mr. A may have no way of identifying that a particular sentence is a Gödel sentence for his own formal system. Thus, contrary to Penrose's claim, it is quite possible that Mr. A is handed a Gödel sentence for his formal system, and has no way to prove or disprove it -- even if it is true. This is because he does not know whether the sentence is a Gödel sentence for his system.

I believe Objection 2 provides a much stronger refutation of Penrose's argument than Objection 1. See here for a more detailed discussion of this issue.

Gödel's Theorem and Artificial Intelligence

In 1931, the mathematician Kurt Gödel published a paper that proved his famous incompleteness theorems. The first of these theorems has the following as one of its consequences: in any consistent axiomatic formal system rich enough to include arithmetic, there are true statements that cannot be proven as theorems. That is, there are statements which are true, but whose truth cannot be determined by any algorithm starting only from the axioms of the system.

Gödel's theorem has had a lot of consequences, though it has not affected the development of most fields of mathematics or science. The theorem has been used by various people to claim various things, including that the Bible is incomplete, that God doesn't exist, and that God must exist. This result has also been used by some people (most notably the mathematical physicist Roger Penrose) to claim that both Strong AI and Weak AI are impossible. I find this claim very interesting, and the arguments that are used are not easy to refute.

I think the arguments are so hard to refute because the natural languages we converse in (English, in this case) are sometimes not nuanced enough to clearly express our thoughts. We use the same phrase to mean two different things and confuse ourselves. The following attempts to address this by highlighting a potential flaw in Penrose's argument. The flaw arises because Penrose fails to distinguish between the knowledge that there exists an object having a certain property from the knowledge of an object having that property. That is, he fails to recognize that we may believe that an object with the property exists, without knowing what the object is.

Gödel's theorems are notoriously hard to grasp. Part of the reason is the unfamiliarity of the setting in which the theorems are developed (first order languages). Luckily, there is a far more familiar setting in which Gödel's theorems come to play under a different guise: that of algorithms and programs, which many people are familiar with today. So let us understand an analogue of Gödel's first theorem in the setting of algorithms, and use this setting to make our arguments, instead of the mathematical logic setting Gödel originally used.

Algorithms and the Halting Problem

Rather than try to define exactly what an algorithm is, I assume that it is well-defined, and note that any algorithm can be encoded as a finite string. An algorithm can have an input and an output; if A is an algorithm with 3 inputs i1, i2, i3, then we use the notation o = A(i1, i2, i3) to indicate that o is the output of the algorithm when executed with the inputs i1, i2, i3. An algorithm can have any number of inputs, and the number of inputs itself needn't be fixed. That is, A could have 3, 4, 66, 1,003,478, or any other number of inputs.

We all know that algorithms execute in a series of "steps", and any program executes a finite number of steps before it halts. We also know that programs sometimes don't halt at all -- an operating system hang, for example, a loop such as "while(1){}" in C, or a program written to halt when it finds an odd number divisible by 2. The Halting Problem refers to the following question. Is there any algorithm A, which, given another algorithm B as input, halts and returns 1 if B halts, and halts and returns 0 if B doesn't halt? That is, A(B) = 0 if B doesn't halt, A(B) = 1 if B does halt. Important points to note:

1. A(B) must halt -- after a finite number of steps, it must stop.
2. The answer it returns (0 or 1) must be correct.
3. A() must be able to do 1. and 2. above for any program B.

The answer to this question is known; there cannot exist any such algorithm A.

HL1: For any algorithm A, there is an algorithm, call it G(A), such that either A doesn't halt on input G(A), or A(G(A)) is wrong (0 if G(A) halts, 1 if G(A) doesn't halt).

We write G(A) instead of just G to emphasize that G(A) depends on A.

Now suppose we insist on considering only algorithms A which either halt with a correct answer (they halt only when they have determined beyond doubt whether their input halts or not), or don't halt at all. These algorithms never return a wrong answer. Let us call these sound algorithms. Note that a sound algorithm never answers incorrectly, no matter what its input. It can be shown that:

HL2: For every sound algorithm A, there exists an algorithm G(A) such that neither G(A) nor A(G(A)) halts.

This result is the analogue of Gödel's first theorem in the setting of algorithms. Note the following:

1. A is a sound algorithm.
2. G(A) doesn't halt; this is a fact.
3. However, A cannot determine the above fact; A(G(A)) does not halt.
   

We are now equipped to state the usual objection to AI based on this analogue of Gödel's theorem.

The Halting Problem and AI

The usual objection to the possibility of Strong and Weak AI based on the halting problem argument goes as follows.

1. Suppose I am a sound algorithm, say A.
   
2. There is an algorithm G(A) which does not halt such that A(G(A)) does not halt.
   
3. However, I know with certainty that G(A) does not halt.
4. Therefore, since I am A, A knows with certainty that G(A) does not halt, and will perform the following:
1. If the input B is not G(A), A can determine whether B halts in a finite number of steps; A does so and returns the correct answer.
2. If the input is G(A), simply return 0 (for "does not halt"). This is correct.
5. Thus:
1. A is sound; we have not violated this assumption.
   
2. A(G(A)) does halt.
   
6. So A(G(A)) does not halt (from 2. above) and A(G(A)) does halt (from 5.2. above), a contradiction.
7. Therefore 1. must be an invalid assumption.
   

Since the only assumption in the above is that I am a sound algorithm, and we have a contradiction, the assumption must be false; that is, I cannot be a sound algorithm.

This "proof" is slightly blurry in steps 4.1 and 4.2, in the sense that G(A) may not be unique. There will be many algorithms satisfying the requirements for G(A). However, this is a non-issue: we could have considered G(A) to be the class of all algorithms satisfying those requirements and used set membership instead of equality, and this issue would have disappeared.

Disproof

This "proof" conceals several points, which we deal with sequentially.

Objection 1. The first objection is to Step 1 in the proof; this is the most common objection to the proof. Why should we suppose that we are sound algorithms? We may be unsound algorithms. Recall that in the first statement of the halting lemma (HL1), we don't know whether G(A) halts or not. So if we are an unsound algorithm A, we don't know whether our G(A) halts or not, and the proof doesn't go through at all. Penrose does try to defend the assumption that we are sound algorithms.

Objection 2. To move on to the next objection, suppose we grant that if we are algorithms, we would have to be sound algorithms. Is the proof correct in this case? This second objection has to do with what A really is. In steps 4.1 and 4.2 of the proof, we would appear to be modifying the algorithm A itself. Since we assumed "I am A", such a modification may not be permissible. In any case, if A is modified to A', then we need to be concerned with G(A'), not with G(A) any longer. However, this objection is weakened by the chance that steps 4.1 and 4.2 could already be part of A, without any modification. That is, the behaviour of A is to check whether its input is G(A) or not, and base its actions on that test.

Objection 3. Next, we grant that A already includes 4.1 and 4.2 and as a consequence these steps do not constitute a modification to the algorithm. This brings us to what I think is the most crucial flaw in the proof. The proof involves the test: "if the input B is G(A)". A crucial question is, would A be able to recognize G(A)? A knows that G(A) exists, but does not know what G(A) is. The knowledge of the existence of G(A) does not enable A to test whether B = G(A). Note also that, as noted below the proof, G(A) is not unique. Thus even if A could find one G(A) and compare B against it, this would not suffice. A would have to compare B against all possible G(A)s -- this could be an infinite set. Thus A would have to determine using some clever method (not simply by comparing against candidates for G(A)) whether B is a valid candidate for G(A). If we assume that A can do this in a finite number of steps, we now have two assumptions in the proof, and the contradiction at the end would only imply that any one of them could be wrong.

Conclusion

Several people have published various versions of this proof, but if it is the proof in the above, it would seem that the fallacy outlined in the third objection settles the issue. As pointed out at the beginning of this article, it is the free form of the English language that makes it so hard to pin down what is really going on. When we say we know that G(A) doesn't halt, we imagine we also know what G(A) is -- this is not the case here. This distinction, between knowing that "there is a G(A) such that G(A) and A(G(A)) don't halt" and knowing that "G(A) doesn't halt", is the crucial one. Weak and Strong AI are still very much alive!