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.