More Interview With Kurt Gödel
Part II of the GLL exclusive
|By permission of Vi Hart, mathemusiciartist: source|
Kurt Gödel has assented to our publishing the second part of the interview we conducted with him a year ago.
We had his assent to begin with, but issues of time are unclear in this type of situation, and with this kind of super-luminary one can never be too careful. We also needed his help in transcribing this second part. What happened is that as the collective human consciousness realized that the discovery of naturally-occurring faster-than-light neutrinos had failed owing to a loose cable, the effect our setup relied on faded and disappeared. Gödel compensated by spinning up enough artificial neutrinos to transmit what was recorded on his end. However, he could not do this until All Hallows Day came around again, which was Thursday.
The first part had glossed over his achievements in logic and set theory. We were delighted that he talked about them in much detail—indeed enough that this post is in two installments. We hope you will be interested. Whether we can get him back for a further interview may depend on your interest, to satisfy the anonymous donor we mentioned in August.
We did not call him Kurt. German speakers of his generation tended not to use first names even with their close friends. As we said, with that kind of person one can never be too careful. Dick conducted the interview while I monitored the transmitter.
Interview, Part II
The second part followed a few hours after the first, when we realized we hadn’t heard much on what “incompleteness” really means. Hence we got right to it when we resumed.
Completeness and Incompleteness
GLL: Good day again Professor Gödel—good afternoon I guess—and danke viel mals for being willing to continue.
Gödel: It is fine—Adele, my wife, lets me sleep late in bed, or even read in bed.
GLL: So it is still morning for you?
Gödel: Morning, afternoon…wie Sie es wünschen.
GLL: Thank you. Professor, our readers would like to know, what is the difference between “completeness” and “incompleteness”—in your famous theorems.
Gödel: Zwischen den Vollständigkeitssatz und den Unvollständigkeitssatz?
GLL: Ja—yes. You prove that all systems of first-order logic that include the predicate calculus are complete, but first-order arithmetic and all stronger systems—which include the predicate calculus—are incomplete.
GLL: How can the same system be complete and incomplete? How can making something stronger make it incomplete?
Gödel: Ach—your words in English are too short. We have longer words so we think more before finishing them. Less confusion.
GLL: Please explain.
Gödel: Sure. The difference is that with arithmetic you build from a single model, the integers, while with general first-order systems you can have any model.
GLL: What is a model?
Gödel: I can explain it without models. Completeness says that if a statement in the system is valid—which means always true—then it has a proof. Incompleteness says that there are some true statements—about integers—that are not provable in the system.
GLL: So isn’t that a contradiction? Surely a true statement–call it —is always true?
Gödel: No, in some situation might not be true.
GLL: But involves only numbers—integers—that was the brilliant point of your using Gödel Numbers. So how can it be true about integers and not be true?
Gödel: It can be true but not valid.
GLL: What’s the difference?
Gödel: Let me try an example. Consider the statement .
GLL: Certainly true.
Gödel: But what if the integers are modulo 3?
GLL: Ah, then . So inequality is not valid. But the integers aren’t modulo 3.
Gödel: Right, but how do you tell your formal system that?
GLL: You add axioms: . And . That does it, now your mod-3 case doesn’t hold.
Gödel: But what happened is you made a theorem. You can deduce it from your axioms. And anything you can deduce is valid—that’s clear—but the opposite is the point of completeness: Anything valid can be deduced.
GLL: I still don’t see why this doesn’t contradict incompleteness.
At this point Gödel sighed. Unfortunately it wasn’t a usual sigh—it was an Al Gore type of sigh, and it overloaded the transmitter. Dick and I decided while we waited that perhaps we should move on to incompleteness. We were afraid Gödel would be impatient with us, but actually he was apologetic.
Gödel: Verzeih mir—I’m sorry—maybe I should define models. I gave such a bad proof in my Ph.D thesis because I didn’t use models.
GLL: A bad proof?
Gödel: Yes it was a good theorem, but a bad proof, and I didn’t learn much until after the war, from Henkin.
GLL: You mean Leon Henkin—another student of Alonzo Church.
Gödel: Yes, and Gisbert Hasenjaeger—who was the German anti-Turing.
Gödel: He found and patched the weaknesses in the Enigma code, not realizing Turing and fellows had broken more of it long before.
GLL: How do you know that? It’s 1971 where you are, and Turing’s WW II role wasn’t declassified until later in the 1970’s.
Gödel: Why should that surprise you? You know how I guard against spies. With that kind of person, one can never be too careful.
GLL: OK, let’s move on to incompleteness.
Gödel: Ach, another bad proof.
GLL: Bad proof? It is considered one of the greatest intellectual achievements of the century.
Gödel: But I did not even get the theorem statement right. Of course consistency is enough, but I was lazy and published what I had and Rosser trumped me.
Gödel: My paper was 100 manuscript pages, and I ended the title with “Part I” because I had another 100 pages in sketches. If a person today claims a big proof in 100 pages and then expands it to 200 pages, what do you think of that?
GLL: You know, John Barkley Rosser’s son—same name—commented in our blog when we had the episode with Vinay Deolalikar’s 100-page proof.
GLL: OK, but there was nothing wrong with your 100 pages, let alone 200.
Gödel: How do you know? Like Principia Mathematica itself, almost nobody read it! They decided it was true based on simpler thinking.
GLL: What makes you think that?
Gödel: The only person I believed really read it was Ernst Zermelo, who thought he found an error, which I replied in 10 pages was not. But he didn’t like it and attacked me instead, so I deduced he didn’t read it. Besides, nobody asked me for the Part II.
GLL: Well yes, people teach your theorem in courses without covering 100 pages.
Gödel: Happily now I can prove everything in half a page.
Dick and I gasped, and this time we upset the apparatus. The image of Gödel flickered but held.
Gödel’s Half-Page Proof
GLL: Sorry. Please proceed, Professor.
Gödel: We build logic with numbers, but the goal is to understand computation. For a formal system to be strong, it must at least be able to recognize whether a string is a full trace of a halting computation. Can be by Turing machine or debugger in your favorite programming language, like Algol or COBOL or the new one, Pascal.
GLL: Many more languages now.
Gödel: No matter, whatever language, if is useful at all then whenever is a halting computation of a program , can be on empty input, proves it. Call the sentence proves . And when is not a full trace, proves .
GLL: OK—like the Kleene -predicate with the empty string.
Gödel: Genau. Of course we assume is consistent, and also effective: we can decide whether a given string is a proof of a theorem. Now define the predicate
So —the set of making true—is the set of non-halting programs.
GLL: Which is undecidable—indeed not even computably enumerable.
Gödel: Finally let
What do you have?
We were being schooled by him—did he ever teach a course at Princeton? At least we knew what to say.
GLL: Since is effective, is computably enumerable. So it can’t be equal to which is not c.e.
Gödel: Can we have an in ?
GLL: If we have, then proves , but so the program really does have a finite halting computation . Thus proves , but also by the rule for , proves . Thus would be inconsistent.
Gödel: Richtig. So is a subset of .
GLL: And by above, a proper subset. So there is a in .
Gödel: And this means?
GLL: The statement is true but not a theorem of .
Gödel: Now this is not quite all of the First Incompleteness Theorem—you also need to make sure is not a theorem of , to make fully independent. For this I stated “omega-consistency,” but for intuition let’s just assume is sound—everything it proves is true. Then that’s it.
GLL: What more do we need for the Second Incompleteness Theorem?
Gödel: Nothing! Well we skip technicality about proof predicates. It’s simply: If could prove its own consistency, then it would prove after all, so it cannot prove its own consistency. Der zweite Unvollständigkeitssatz.
GLL: Does this work with any predicate that defines a non-c.e. set? Such as program halts for all inputs. It always has instances that are true but not provable.
Gödel: But when is not co-c.e., is assuming consistency enough? Your readers may also enjoy trying to find that makes Rosser’s version work, both sides needing only consistency. Anyway, finally this explains the Completeness Theorem.
GLL: You mean Incompleteness Theorem.
At this point I came in front of his monitoring station to say something, but this disturbed the transmitter and we lost the rest of what Gödel said. Happily he came back before we did anything. He was excited and pressed forward so that his head filled the screen—it felt like the movie “The Wizard of Oz.”
Completeness and the Infinite Halting Machine
Gödel: Now consider the statement again, which cannot prove. Is it valid?
GLL: It is true…
Gödel: But by Completeness, if it were valid it would be a theorem!
GLL: So it isn’t true?
Gödel: Yes it is true. It just isn’t valid.
GLL: The program —say it’s a Turing machine on empty input—never halts, right?
Gödel: Yes and there is a simple arithmetical formula that codes saying this. Doesn’t matter Turing machines or Algol or Pascal or even APL. This is what people decide is true without reading boring details—except those who write interpreters or compilers that hopefully have no bugs. Always just a sentence about integers. A true sentence.
GLL: How can that not be valid? You mean if the integers were mod 3 again?
Gödel: No, we built in your previous axioms already. is a strong system, remember? One you use to prove real theorems, and verify programs, like that.
GLL: What if I add more axioms?
Gödel: Can’t—you fixed to begin with. It’s like saying oops you forgot to put Cantor’s diagonal number in your list of reals. No oops.
GLL: So what happens if is not valid?
Gödel: Well, I said that then the statement is consistent with the system . That is, is consistent, though no longer sound. But Henkin said something better.
GLL: What did he say?
Gödel: He showed that has a model—a structure in which every axiom of is true, every theorem of is true, and also is true.
GLL: But is the same as numbers, right?
Gödel: It has all the numbers: , and , and , , and all the negative integers with their usual properties like .
GLL: So what’s the trouble?
Gödel: It has extra numbers. Positive numbers that are above all the ones in , and their negatives.
GLL: But anyway if is true it means the machine halts, which it must do in some number of steps…
Gödel: Indeed, but not necessarily in some finite number of steps. It can be one of those other, non-standard numbers of steps.
GLL: So can halt after infinitely many steps?
Gödel: It’s like counting up to , or any non-limit ordinal.
GLL: But a Turing machine is not an ordinal. If I run , it will never halt.
Gödel: It will non-standardly halt. It will have a halting part that majorizes the non-halting parts.
GLL: Turing machines don’t run like that. You have to run them from the beginning.
Gödel: It follows from Completeness and Incompleteness that they must run like that. Because we have defined computation in terms of numbers. Abraham Robinson made non-standard analysis out of these numbers—you can have non-standard computation. Perhaps it will help you understand why it is hard to find a proof of —or the reverse.
Dick and I exchanged quizzical glances—we had not expected our intuition about computation to be upset like that. I was also surprised by Gödel’s objective approach to truth—he didn’t say it was relative to axioms or mention relative consistency, and he shied away from models. He didn’t sound much different from David Hilbert.
Viewing the time, we moved on to Set Theory. We will post the rest of the interview shortly—Gödel added some things in his Thursday re-send about large cardinals, the meaning of completeness, and Alexander Grothendieck that we don’t understand, and we are trying to learn them before we post.
To Be Continued…
Did Kurt’s explanation of major results in logic help you understand them? Or did it leave you unsettled?
[simplified to read , changed pic of Gödel]