← Home

The Gödel Argument

The theorem starts with “if the system is consistent”. They skipped that bit.

Gödel in four paragraphs

A formal system is a fixed list of axioms plus fixed rules for deriving things from them. Turn the handle and out come theorems. Call the system F. A machine that does mathematics is the same thing: whatever program it runs, the statements it will ever announce as true are the theorems of some F. So “is the mind a machine?” becomes “is there an F that captures everything a human mathematician can prove?”

F is consistent if it never proves a contradiction. It is sound if everything it proves is actually true, which is asking for more.

Gödel showed how to build, for any F that can do arithmetic, a sentence that in effect says “F cannot prove this sentence”. Call it G(F). His first theorem: if F is consistent, then F can’t prove G(F), and so G(F) is true. His second theorem: if F is consistent, F can’t prove that it is consistent.

The argument below is that you, looking at F from outside, can see that G(F) is true, while F is stuck. Do that for every possible F and no F can be you.

The argument, in their words

Lucas, in Philosophy, 1961:

Gödel’s theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines. — Lucas (1961)

… given any machine which is consistent and capable of doing simple arithmetic, there is a formula which it is incapable of producing as being true — i.e., the formula is unprovable-in-the-system — but which we can see to be true. It follows that no machine can be a complete or adequate model of the mind, that minds are essentially different from machines. — Lucas (1961)

Penrose wrote two books on it. His own compressed version is from his 1996 reply to critics. Suppose some F captures all of human mathematical reasoning, so that in effect “I am F”. F′ is F with the statement “I am F” added as an extra axiom, and G(F′) is its Gödel sentence:

Though I don’t know that I necessarily am F, I conclude that if I were, then the system F would have to be sound and, more to the point, F′ would have to be sound, where F′ is F supplemented by the further assertion “I am F”. I perceive that it follows from the assumption that I am F that the Gödel statement G(F′) would have to be true and, furthermore, that it would not be a consequence of F′. … Since I am therefore capable of perceiving something beyond the powers of F′, I deduce that, I cannot be F after all. — Penrose (1996)

His conclusion is that the brain does something no computer can, so physics must contain something non-computable, and he thinks it lives in quantum gravity acting on microtubules in your neurons. I am not making that up.

Rebuke 1: the theorem says “if”

Gödel did not prove that G(F) is true. He proved: if F is consistent, then G(F) is true and F can’t prove it. If F is inconsistent it proves everything, G(F) included, and G(F) is false. Look at Lucas’s own sentence. The word “consistent” is right there, and then it quietly vanishes before the conclusion.

What can a human actually “see”? The conditional: if F is consistent then G(F). F can see that too. The conditional is a theorem of F; proving it inside F is exactly how Gödel’s second theorem is derived. So on the only thing anybody can actually see, human and machine are dead level.

To get G(F) outright you need to know F is consistent. The second theorem says F can’t prove that about itself. Fine. Can you? For F equal to Peano arithmetic (the usual axioms for the whole numbers), sure, you believe it, because you have the natural numbers in mind. A machine can believe it as well: add “F is consistent” as an axiom. It is one line.

Now it proves G(F), and it has a new Gödel sentence, and so do you, because you don’t know that your new, bigger set of beliefs is consistent either. Nobody knows that ZFC, the axioms underneath nearly all of modern mathematics, is consistent. We just haven’t found the contradiction yet.

So the argument needs an extra premise: humans can know that they themselves are consistent. Nothing supports it, and history is against it. Frege’s system was inconsistent and he was about to publish volume two when Russell’s letter arrived. Naive set theory was inconsistent and the best mathematicians alive were happily using it.

Turing had already said it all in one sentence in 1950:

… although it is established that there are limitations to the powers of any particular machine, it has only been stated, without any sort of proof, that no such limitations apply to the human intellect. — Turing (1950)

Lucas’s response

He saw the consistency problem coming, and this is what he did with it:

Nor could we make its inconsistency a reproach to it — are not men inconsistent too? Certainly women are, and politicians; and even male non-politicians contradict themselves sometimes, and a single inconsistency is enough to make a system inconsistent. The fact that we are all sometimes inconsistent cannot be gainsaid, but from this it does not follow that we are tantamount to inconsistent systems. Our inconsistencies are mistakes rather than set policies. … Human beings, although not perfectly consistent, are not so much inconsistent as fallible. — Lucas (1961)

Leaving aside the women, this concedes the point. “Fallible but we fix it when we notice” describes a system that does not know it is consistent. Frege didn’t have a set policy of contradiction either. He just had one, and needed somebody else to find it.

Rebuke 2: go on then, do it

Lucas pictures a contest. You hand him a machine, he hands you back its Gödel sentence and declares it true. This works nicely when the machine is Peano arithmetic, which fits on a postcard.

The candidate for your mind is not a postcard. It is a formal description of something with around 10¹¹ neurons and 10¹⁴ synapses. Nobody can write it down, let alone read it, let alone look at it and see that it is consistent. And without that, you see nothing about its Gödel sentence. It is the Chinese Room mistake again: build your intuition on a toy, then apply it to something a dozen orders of magnitude larger.

In fact humans demonstrably do not have the power the argument needs. “This system is consistent” is the same kind of statement as “this program never halts”: the program being the one that grinds through F’s proofs looking for a contradiction. There is a Turing machine with a few thousand states that halts if and only if Goldbach’s conjecture is false, and another of similar size whose behaviour cannot be settled by the standard axioms of mathematics at all. If mathematical insight can see these truths, would somebody please tell us the answers. Human insight is not an oracle that looks at a program and sees whether it ever stops. It is a mathematician staring at a whiteboard for thirty years and sometimes getting somewhere.

Penrose’s response

On human error, he retreats from mathematicians to an idealised mathematician:

I fully accept that individual mathematicians can frequently make errors … This is not the point. Mathematical errors are in principle correctable, and I was concerned mainly with the ideal of what can indeed be perceived in principle by mathematical understanding and insight. — Penrose (1996)

And then, two paragraphs later:

We must ask whether it is conceivable that this mathematical community, or its individual members, could be entirely computational entities even though the ideal for which they strive is beyond computation. Put in this way, it may perhaps seem not unreasonable that this could be the case. — Penrose (1996)

Quite. The ideal mathematician who never errs and sees every truth in principle is not a person. It is a definition. Every actual mathematician, the only kind whose brain needs explaining, could be “entirely computational” by his own admission. That is the whole case, conceded in a subordinate clause.

On the objection that we could be an algorithm without knowing which one, or knowing that it is sound, he notes with some satisfaction that nobody disputes this conclusion:

Human mathematicians are not using a knowably sound algorithm in order to ascertain mathematical truth. — Penrose (1996), quoting Shadows p. 76

Nobody disputes it because it is harmless. “Not a knowably sound algorithm” leaves “an algorithm, not knowably sound” wide open. That describes every piece of software ever shipped, and me.

Rebuke 3: Gödel didn’t think his theorem proved it

Gödel thought about what his theorem meant for minds and machines, and he was careful where Lucas and Penrose are not. What he claimed followed was a disjunction:

… either … the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems … — Gödel, Gibbs Lecture (1951)

Either we beat every machine, or there are mathematical questions we will never answer. Gödel personally leaned towards the first. But he knew the difference between what he believed and what he had proved, which is the entire problem here. The Lucas–Penrose argument is what you get by deleting the second half, and given the whiteboard evidence the second half is looking pretty healthy.

Rebuke 4: when your conclusion needs new physics, check your argument

Penrose, to his credit, follows the logic where it leads. If mathematicians do something non-computable then brains do, so physics does, and since no known physics is non-computable there must be new physics: an objective collapse of the wave function driven by gravity, orchestrated in neuronal microtubules. Tegmark calculated how long quantum coherence would survive in a warm, wet brain and got somewhere between 10⁻¹³ and 10⁻²⁰ seconds. Neurons work on milliseconds.

Most people, on finding that their argument about logic requires rewriting quantum mechanics inside the cytoskeleton, would go back and look for a missing “if”.

In their favour

We can’t be an algorithm that we know to be sound. True, and interesting. A mind can’t fully certify itself. That is a fact about self-knowledge, not about machines.

Gödel’s disjunction is real mathematics and still open.

And Penrose is one of the great mathematical physicists, with a Nobel Prize for the part of his work that involves checking the hypotheses.

References

• Lucas, J. R. (1961). “Minds, Machines and Gödel.” Philosophy 36(137), 112–127.
• Penrose, R. (1989). The Emperor’s New Mind. Oxford University Press. Penrose, R. (1994). Shadows of the Mind. Oxford University Press.
• Penrose, R. (1996). “Beyond the Doubting of a Shadow: A Reply to Commentaries on Shadows of the Mind.” Psyche 2(23). His replies to Chalmers, Feferman, McDermott and others.
• Turing, A. M. (1950). “Computing Machinery and Intelligence.” Mind 59(236), 433–460. See “The Mathematical Objection”.
• Gödel, K. (1951). “Some Basic Theorems on the Foundations of Mathematics and Their Implications” (the Gibbs Lecture). In Collected Works, vol. III, Oxford University Press, 1995.
• Feferman, S. (1995). “Penrose’s Gödelian Argument.” Psyche 2(7). Chalmers, D. J. (1995). “Minds, Machines, and Mathematics.” Psyche 2(9).
• Franzén, T. (2005). Gödel’s Theorem: An Incomplete Guide to Its Use and Abuse. A K Peters.
• Yedidia, A., and Aaronson, S. (2016). “A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory.” Complex Systems 25(4). arXiv:1605.04343.
• Tegmark, M. (2000). “Importance of Quantum Decoherence in Brain Processes.” Physical Review E 61(4), 4194–4206.