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.

Strong and Weak Artificial Intelligence

Artificial Intelligence (AI) is almost an umbrella term today. Different people use it to refer to different things, and all of the uses taken together cover a lot of ground. Image processing, pattern recognition, various types of automated statistical analysis and syntactic reasoning have all been called artificial intelligence.

The AI of this article refers to the ideal of creating a computer with human-like behaviour or consciousness. That last sentence is already a loaded one. To some people, creating human-like behaviour is the same as creating human-like consciousness. Others argue that behaviour and consciousness are fundamentally different. The two are called, respectively, Weak AI and Strong AI.

Weak AI refers to the ideal of creating, via artificial means (artificial meaning demonstrably algorithmic, for instance via a program on a computer), a set of behaviours which are indistinguishable from human behaviour.

Strong AI refers to the notion that the human mind is in fact algorithmic. Not only can it be simulated using an algorithm, it is an algorithm.

Distinguishing between Weak AI and Strong AI can be hard. Although they appear to be different, the argument goes that if something behaves exactly like a human, then it is human, at least mentally. This may seem counterintuitive at first, but the crucial condition is that it behave like a human in all aspects. If this argument is accepted, then simulating something that behaves like a human is the same thing as creating a human. To understand this point of view, it helps to try to identify the difference between a "true" human and a "simulated" human from the mental perspective. Is there any aspect of the mentality of humans that cannot be simulated, which does not manifest in any form of behaviour? That is, is there anything about the mentality of humans that is not "simulatable", even if every part of the behaviour is simulatable?

Opponents of the equality of Strong AI and Weak AI use arguments based essentially on the philosophical notion of qualia, or unique individual perceptions. For example, an organism experiencing pain has a unique, unified experience of the sensation. Opponents of the equality essentially claim that such an experience or quale cannot be simulated on a computer, even if the behaviour associated with the experience can.

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!

The Chinese Room Experiment - Part I

The Chinese Room Experiment is a thought experiment building on the Turing Test put forward by the philosopher John R. Searle.

The intention of the thought experiment is to demonstrate that the hypothesis of Strong Artificial Intelligence (Strong AI), which claims that the human mind is an algorithm, is wrong. The Strong AI argument says that every human mental process is algorithmic, that is, it follows a predefined sequence of steps. This appears to be different from the Weak AI hypothesis, which claims that every human mental process can be simulated on a computer, but that the human mind itself is not an algorithm. Some argue that mental processes are essentially particular behaviours (behaviouralism) or a way of looking at physical processes (functionalism), and as a consequence there is no significant distinction between the Strong AI and Weak AI hypotheses. (Read about Strong and Weak AI.)

The Chinese Room Argument asks one to imagine that there is a native English speaker, Steve, sitting in a closed room with two windows. Steve knows nothing of Chinese. In the room is a book containing detailed information on how to respond to any sentence in Chinese. Outside the room is Wong, a native Chinese speaker. Steve receives a sentence in Chinese from Wong via the input window, consults the book, and responds in Chinese at the output window. Steve carries on such a conversation with Wong without understanding either the input, the output, or the logic behind the exchange.

Searle claims that to Wong, Steve would appear to "know", or "understand", Chinese. But Steve doesn't. He is simply following an algorithm; he has no clue what any of the Chinese exchange means. Thus, according to Searle, no algorithm constitutes understanding or consciousness.

Objections to the Chinese Room Argument

There are several answers to Searle's Chinese Room Experiment from people claiming that it does not prove the impossibility of Strong AI. Here are some of them:

1. The Systems Reply
   
1. Objection This objection says that, while Steve does not understand Chinese, the system consisting of Steve and the book does. This can be viewed as a single, larger entity which does understand Chinese.
2. Searle's Reply Searle replies to this objection by suggesting a modification of the experiment in which Steve memorizes the entire translation book and steps out of the room, talking face to face with Wong. Steve still does not understand Chinese, says Searle. He is still applying the rules without any understanding of Chinese.
3. Rejoinder The problem with Searle's reply is that it invites us to think of all of Steve's memory as an integral part of his consciousness or ego, while in this modification to the experiment, Steve is using his memory as if it were just separate storage, no different than copying the book onto his forearm. Steve and his memory, taken together as a system, do understand Chinese.
   
2. The Complexity Reply
1. Objection This objection, due to Daniel Dennett, says that it is not easy to duplicate consciousness without being extremely complex. Ignoring this complexity in the Chinese Room Experiment fools our intuition into thinking the Steve+Book combination is ignorant of Chinese, since we think the book is "just a book". In fact, if we considered the complexity of the algorithm required to converse in Chinese, we would be forced to conclude that the "book" is actually complex enough to be considered conscious. (The notion of a book being conscious may seem ridiculous, but this really refers to the algorithm contained in the book, not the physical book itself.)
2. Searle's Reply Searle interprets Dennett's objection as the statement "You can't have a book like that", and goes on to say that the whole point of thought experiments is to imagine a situation that is conceivable, even if it we don't know the details of how to set it up. He says Dennett is essentially denying the idea behind thought experiments.
   
3. Rejoinder Dennett is not saying it is impossible to have a book that complex; he is saying anything that complex is already conscious and aware. If Searle insists on having a thought experiment where a book is complex enough to converse in Chinese but is not conscious, he is assuming too much and is begging the question.

More information on this interesting topic can be found in the following books:

Consciousness Explained - by Daniel Dennett
The Mystery of Consciousness - by John R. Searle