Skip to content

A GLL exclusive

Kurt Gödel is the subject of today’s special post.

I recently had the pleasure of interviewing Gödel, and this post is the slightly edited version of part of that interview.

Of course Gödel passed away in 1978. However, Ken and I have had a promising first month on a six-month project to overcome factors like that, using Gödel’s own work on relativity and some recent developments in physics. We will report on this right after the project’s end date of March 31${{}^{st}}$, 2012.

Unlike standard time machines, ours does not have any notion of “traveling” or “returning to the past” to visit one’s grandfather, and thus avoids the usual paradoxes. The returner does not move back in time, nor does the visitee move forward. Instead the machine arranges that both can interact in some frozen place—it has to be about 1.9 degrees Kelvin. The person from the past does not remember anything definite about the interaction, while the returner—who is really a receiver—recalls all. When the two “meet” it is as if they can see each other and chat normally. For reasons having to do with quantum physiology this can be done only for a few 20-30 minute sessions with any one person.

We did obtain Gödel’s permission to do this—or rather, he gave permission forty years ago, and specifically only at this time of year. Halloween is so called because it is the evening of All Hallows, which is a name for All Saints’ Day. We don’t yet know if anyone else has given this permission. We welcome any comments on other travelers.

## The Interview

This is a partial record of our interview with Kurt Gödel. I am transcribing the rest, and will put that out shortly.

## Incompleteness Theorem

GLL: Good morning Professor Gödel, it is an extreme honor to finally meet you, and I hope your “journey” was not too uncomfortable.

Gödel: Well, I’m as comfortable as if I were in my own bed, as I think the expression goes. It’s you coming back to find me in 1971 I should be concerned about.

GLL: It’s late 2011 where I came from, and I don’t know what time I should say it is here. I’m glad you are well—you look pale and ghostly but maybe it’s the image.

Gödel: I dined at a restaurant and felt queasy afterward—I wonder, are you with the government? Never mind, you will say no anyway. I am very concerned about the flaws in your Constitution, and I conclude that I shouldn’t eat out. Anyway, I can see you.

GLL: Professor—as you know we do not have much time, so could we please proceed with the interview?

Gödel: Fine.

GLL: Thank you. Your famous Incompleteness Theorems are considered among the great results of all time. Could you tell us how you came to think about them?

Gödel: I was quite influenced by Hilbert’s program to prove mathematics consistent. After I proved the Completeness Theorem I started to try and see if I could prove there was a model of arithmetic. But when I started to look at the question in detail it seemed that there was a fundamental roadblock.

GLL: Did you try to prove that ${\mathbb{N}}$ was a model?

Gödel: No—I already had a theorem telling me not to try. You know I had Tarski’s theorem on undefinability of truth in ${\mathbb{N}}$ already in 1930. So I tried to make a model from the syntax, using my numbering ideas to extend what I did for first-order logic.

GLL: Did you have the so-called Second Incompleteness Theorem right away?

Gödel: I felt I could prove something like that, but I was concentrating on the details of the main proof. I had to develop the entire theory of recursive functions from scratch, which was quite tedious.

GLL: We understand. Your style in all of your great results has been to give almost complete details, but the Second Incompleteness Theorem you only sketched. Is there a reason?

Gödel: I thought it was pretty routine. I was a bit surprised however when John von Neumann sent me a letter stating this as a theorem. I was a bit worried that he might claim it, but he was quite nice about that.

GLL: Did you ever meet Alan Turing?

Gödel: No, I never had the pleasure. I thought we might meet at the IAS in 1939, but Turing had left and with the war I had to go later via Vladivostok.

GLL: Turing developed an alternative to your definition of recursive functions, which is based on a kind of mechanical machine, which we now call a Turing Machine.

Gödel: Of course I know Turing machines. They were useful to prove that basic first-order logic is undecidable. I see one of your friends repeated that proof in a paper.

GLL: You mean Steve Cook?

Gödel: Yes, and obviously it’s a many-one reduction. You young people publish too quickly.

GLL: We use Turing machines now as the basis for computational complexity.

Gödel: Why? They don’t do anything useful for humans! Johnny had ideas, and Konrad Zuse, and at least people built real machines with them. Yes, Turing had a correct definition for computability by a machine, but you need computability by a human in order to prove things. I think based on Turing machines you won’t be able to prove any meaningful lower bounds. But yes, to define a problem they are good.

GLL: Do you dream of Turing machines?

Gödel: What do you think I am, a madman?

[We learned that it is not a good idea to get the subject excited, as there was a break in transmission. When we re-established it, we changed the topic.]

## The “Lost Letter”

GLL: Sorry, beg your pardon, Professor. I did not mean to offend.

Gödel: No offense taken, it’s just that popular images$\dots$ I talked to Albert about this, the photo with his tongue sticking out, not combing his hair. Not anständig, not dignified. Marilyn Monroe never did that.

GLL: The letter that you sent to John von Neumann on a possible algorithm for the propositional calculus was very prescient. You raised what is still, fifty-plus years later, one of the fundamental questions in all of mathematics. It is called the ${\mathsf{P} = \mathsf{NP}}$ question.

Gödel: I do recall the letter, and I thought the question would cheer him up. It was a sad time—Johnny was so ill. So there is no good algorithm that decides propositions?

GLL: None that is known. The conventional wisdom today is that there is no such algorithm, but that is wide open.

Gödel: Interesting.

GLL: Many of us wonder why you did not write a paper that would have raised the question. It took fifteen years for Cook to rediscover it.

Gödel: My view on publishing was always to get the result worked out in full. I thought about the question some, but since I could not make a definitive statement I decided to wait.

GLL: What did you think the answer would be?

Gödel: Well I thought the important point was, can you do it in a tableau of size no worse than the square of the number of variables? If the formula is not too big—well you can assume each variable occurs a bounded number of times, and maybe ignore labels so the symbols grow like ${n}$ too. If you need ${n^3}$ not ${n^2}$ size maybe I can see a reason with triangles, but beyond ${n^3}$ it is meaningless.

GLL: Today we say any ${n^c}$ time is good.

Gödel: Really? When I wrote to Johnny I thought ${k\cdot n}$ means you understand the solution, ${k\cdot n^2}$ means you can solve it but only partly understand it. Of course ${N}$ means you have no understanding at all.

GLL: ${N}$?

Gödel: ${N}$ means exponential in ${n}$. Johnny showed that quantum mechanics could be expressed completely with linear operators, not quadratic forms like Hilbert tried to do. If you make everything finite and write out the operator as a matrix you get a big ${N \times N}$ but the information is only ${n}$, so of course that is not how to understand it. Dirac helped with his bra-ket notation but needed his ${\delta}$ function to write the underlying equations which of course is not in Nature. So Johnny tried to avoid it all—-so sad he did not try again. Anyway “${N}$” always got the laugh from Johnny.

[Once again we learned it is not a good idea to make the subject laugh either. We had to start over—luckily the disturbance did not last long.]

## Time Travel

GLL: We feel we must mention that you once worked on time travel. I believe it was the only paper your ever published on General Relativity. How did you come to think about this?

Gödel: I spent much of my time with Einstein, and it was natural to begin to think about his work. I wrote a second paper, but mostly it was published by two other people because I wasn’t sure.

GLL: What was the second paper?

Gödel: It was contradicting the first one, well if space expands like for ${\Lambda \geq 0}$.

GLL: We just had the Physics Nobel Prize for the people who showed ${\Lambda > 0}$.

Gödel: Strictly greater?

GLL: Yes—confirmed by several experiments now.

Gödel: This means that in the future people will have no ability to prove the Big Bang happened by observation, only memory. Every galaxy cluster will be completely isolated in totally cold space. Unless time travel is possible even with ${\Lambda > 0}$.

GLL: You proved it is possible. Well, we are proving it. How did you do it?

Gödel: I only proved it for ${\Lambda < 0}$. Then the idea is simple.

GLL: Can you please explain for our readers?

Gödel: As you know acceleration is equivalent to gravity, but it is not relative like regular motion. If one twin accelerates and comes back, it is he who stays younger—it is not correct to say there is the same description where he stayed still and the other twin accelerated. Now more difficult case is when you spin around. Angular motion is always acceleration, going faster in some coordinates and slower in others up and down, but unlike linear acceleration you can keep on doing it. In both cases the question is, is this relative to all the matter in the universe or is it absolute? This is Mach’s Principle, really a question. What I show is if you have a rigidly rotating universe, then the fact of keeping on going means if you are far enough from the center you can go backwards in time—like if you could go faster than ${c}$ with no limit—but this needs also pressure on the universe together, i.e. ${\Lambda < 0}$.

GLL: ?

Gödel: OK so ${\Lambda > 0}$, but maybe you have found some local condition on a tiny scale with spinning particles and enough shielding$\dots$

GLL: Are you still working on this now?

Gödel: I wish to, but I don’t have Einstein, and even he wouldn’t believe me or Johnny! About quantum. Quantum is the way of going around in a circle, relativity is going in a straight line. These two ways are what we need to unify, but Albert wouldn’t believe me—he kept writing equations rather than thinking about concepts. Not like the old Einstein, but he was mad it took him 12 years to finish one equation! Anyway it is a hard problem, and I am working on a bigger one.

GLL: What is that?

Gödel: It is the notion of collection. Every ordinal is either a ${+1}$ step, or it is a collection. You can say each finite cardinal ${n}$ is also the collection of ${0}$ through ${n-1}$. The first uncountable ordinal is the collection of all the countable ones—and it exists by that idea, we don’t care if it is the same as the cardinal of ${\mathbb{R}}$ which we cannot prove anyway. You don’t have to collect as much as Johnny did, just what you know you have. Step and collection, that makes everything, and step is human so collection becomes the most important idea in the universe, especially an ultimate collection.

GLL: We are just talking on our blog about not believing your first collection step, let alone an ultimate one.

Gödel: Well, you don’t have to believe in it! You only have to agree it is possible. Then I can prove for you that it is necessary! In fact my proof is in a language by Arthur Prior which is good for thinking about computation—why do you use Turing machines? Anyway the proof is really centuries old.

GLL: By old you mean the Greeks?

Gödel: Not that old. St. Anselm of Aosta 900 years ago, and then in a better form by Leibniz. That is one message I can give to your readers—look at the ideas of the old greats, they can save you more than half the work of proving things, not just seeing what they thought was important.

GLL: Thank you very much, Professor Gödel.

Gödel: You are welcome to ask more, maybe later. Auf Wieder…–sehen?

GLL: Sehen—ja, Danke, Professor.

## Open Questions

Would you all like to see the continuation of the interview? There is a bit of work transcribing it, since every time you play it back, the recording needs to be shot through a few hundred miles of rock into a vat of emulsion called the Ultima Sieve.

Also, should we use this time machine to interview additional people from the past? Whom would you like to see interviewed the most? One issue however is, how can we transmit back in time to contact people for how to give permission to transmit back in time to contact them?

[fixed Gödel’s account of his rotating universe (singular).]

44 Comments leave one →
1. October 31, 2011 3:28 pm

The views and opinions expressed in this interview are strictly those of Kurt Friedrich Gödel, and do not necessarily reflect the views or policies of the Georgia Institute of Technology or the University at Buffalo, The State University of New York. Happy Halloween!

Sources and supporting remarks.

2. October 31, 2011 4:31 pm

Personally I think it is highly valuable to see many of these ideas in their historical context. When presented in a lecture or a textbook they appear seamless, but when you delve into the history you get a real sense of the bumps, cracks and underlying issues. Although mathematics is rigorous, there were paths not taken and issues tucked quietly into the corners, lost while the masses pressed forward. Some of these may hold important clues for the future …

Paul.

3. Craig permalink
October 31, 2011 5:08 pm

In the spirit of the last post on poker, I ask you to show your hand. You are bluffing. Godel never gave you permission to do this interview, right?

4. Javaid Aslam permalink
October 31, 2011 5:47 pm

It is amazing to see that GLL authors can be professional story writers too!

5. I. Ouranos permalink
October 31, 2011 6:01 pm

Great post! I don’t think, actually, that it represents the intense idiosyncrasy of K. Godel, however the content of the interview is very very interesting! Concerning the Open Questions part, i would like very much to see interviewd Paul Erdos…

6. October 31, 2011 7:27 pm

Very, very interesting! 1) Would you be so kind as to ask Prof Gödel about Incompleteness Theorem: it has to use for formal systems only, or it may be used for philosophy also? ;) 2) The fragment: “Turing machines now as the basis for computational complexity” seems to be incomplete IMHO.

7. October 31, 2011 7:57 pm

3) Happy Hallowe’en! :)

8. October 31, 2011 9:27 pm

You should definitely interview Feynman and ask if P=NP.

9. Gender Bender permalink
October 31, 2011 9:47 pm

No one has ever met anyone from the future so the logical assumption is no one ever will.

10. October 31, 2011 9:55 pm

Interesting. It is more learn-able than just imagination.

11. Student permalink
October 31, 2011 10:55 pm

One Question Professor
GLL: Did you try to prove that {\mathbb{N}} was a model?
Godel: You know I had Tarski’s theorem on undefinability of truth in {\mathbb{N}} already in 1930

Could you elaborate a little more? Maybe some references (understandable to someone with an understanding of undergraduate computational complexity).

Sorry if this comes across as too demanding

12. November 1, 2011 12:31 am

I found this to be exceptionally good. Thanks! Just reading it makes me feel smarter. (Kind of like Scott A’s Demosthenes lectures.)

If you can do a few more of these I would buy a book of them. But even as a one-of-a-kind thing this was really nice.

(Interview with Erdos *would* be cool.)

13. November 1, 2011 12:40 am

(Democritus, not Demosthenes. I guess I didn’t really get smarter. I just feel smarter.)

14. November 1, 2011 2:19 am

Very interesting and thought-provoking. Yes, we would like more interviews. Interview Einstein on how he became genius? Of course not genius in plagiarizing the work of Poincare, Lorentz and Hilbert.

15. Tom permalink
November 1, 2011 12:35 pm

Could you interview Fermat? I’d love to know his “truly marvelous proof.”

16. Nasreddin Y permalink
November 1, 2011 2:04 pm

“Unlike standard time machines, ours does not have any notion of “traveling” or “returning to the past” to visit one’s grandfather, and thus avoids the usual paradoxes.”

I noticed the premises you carefullty put for the stage :) You were well advised, indeed, Gödel wouldn’t accept the inteview if you violate his famous theorem about time travelling in the past. Genius idea to meet him not in the past but instead somewhere else … Next time would you please get his own words about a question asked by M. Davis (*) I am eager to know … Thank you for this captivating blog.

* Davis, M. [1982], “Why Gödel didn’t have Church’s Thesis”, Information and Control 54, 3–24.

17. asgasgasgasg permalink
November 3, 2011 12:03 am

Since everyone else seems to be voicing their satisfaction with the latest round of posts, let me voice my dissatisfaction. Lately, GLL posts have been largely content-free. Who on earth doesn’t know about Godel, but can follow the technical content in the rest of the posts on this blog? What is the point in engaging crackpots who don’t believe Cantor’s Theorem, not once, but twice? It is not surprising that there are surprising consequences when you deny Cantor’s Theorem, because it’s a contradiction, and you can prove whatever you want under such circumstances.

I didn’t think the Peano post was too bad, but seriously, I would bet my life that Peano Arithmetic is consistent. The minute I saw that headline, I thought, “OK, but it isn’t”, and…

I think you guys can do better than this.

• rjlipton permalink*
November 3, 2011 5:43 pm

asgasgasgasg,

We try are best. Many of the posts we do are new math—original stuff. We also try to have fun. We also try to inform. The reason for the Cantor post was to answer a continuing question we seem to get about that famous theorem.

We appreciate your comment and will try to up the technical content in the future, at least for some of the posts. We still like to post fun ones, and we hope that is okay.

• Javaid Aslam permalink
November 4, 2011 1:28 pm

And without that little fun we all will eventually be drained out!
Moreover it helps our “souls” to keep in touch with the great “souls” such as Godel.

18. Serge Ganachaud permalink
November 3, 2011 10:04 am

> You should definitely interview Feynman and ask if P=NP.

Marcos,

Feynman was apparently able to answer this problem from a physical point of view. For him, in order to find something you basically had to perform the search. This is what his physicist’s intuition told him.

But I think it’s a mistake to believe that it’s a consequence of P!=NP. Feynman most likely had no clue about this mathematical problem. You can have P=NP but with a smallest efficient program that can solve SAT or factor integers be not executable… simply because it’s number of instructions is larger than the number of particles in the universe. That program could well be as huge as, say 2^{2^1000} instructions long.

I now believe that P=NP, but I think it’s a mistake to draw consequences on what computers can do from this arithmetical statement. Computer processes are objects of physics, and as such they have to obey the laws of physics. For instance, the existence of irreversible processes is a law of nature, and this is why one-way functions do exist in computer science. They probably have an efficient inverse in the standard model of PA, but the corresponding Turing machine isn’t executable because it’s much too big to fit into the memory of a computer.

• Cem Say permalink
November 5, 2011 4:07 pm

> You should definitely interview Feynman and ask if P=NP.

As is usually the case, Scott A. was there before us: http://www.scottaaronson.com/democritus/lec6.html

• November 5, 2011 4:22 pm

“Everyone knows what a curve is, until he has studied enough mathematics to become confused through the countless number of possible exceptions.”

— Felix Klein

Klein’s caveat regarding curves applies with redoubled force to those complexity classes whose membership is validated via oracles. Thus intuitive notions of curves, and intuitive notions of complexity classes, similarly are best embraced with caution.

• Serge Ganachaud permalink
November 5, 2011 5:28 pm

Contrary to him, all that Scott says in his page tends to convince me that P=NP. The common mistake is to associate P with feasible. That’s true of the programs that we humans usually write, but not of all possible ones! I think we’d better look at the thermodynamics of processes. In any case, my hypothesis is an explanation for P=NP and P!=NP being both unprovable – though the former might still be proven indirectly.

19. November 3, 2011 1:07 pm

I would very much like the interview to continue by asking:

“Herr Gödel, do the natural definitions of the complexity classes $P$ and $NP$, and the relativization theorems that constrain proof strategies for proving $P \ne NP$, depend essentially upon the Axiom of Choice (AC)? If so, might we 21st century researchers approach nearer to your vision of Platonic truth in mathematics, by declining the AC, and amending the definitions of $P$ and $NP$, so as to create an axiomatization of complexity theory in which relativization proofs are nugatory?”

More broadly we might ask:

“Herr Gödel, in your life beyond this world, do your favorite proofs require the Axiom of Choice?”

And I will convey my own opinion via an Iowa farmer joke:

“In Iowa we like both kinds of music: Country and Western.”

:)

• November 3, 2011 2:25 pm

PS: Somewhat to my surprise, the arxiv server’s full-text search finds 23 preprints referring to “complexity theory” and “axiom of choice” … of which 5 are multiple-author preprints that display impressive technical depth and set-theoretic sophistication … in other words, they’re utterly beyond my comprehension.

Given that there is (apparently) some natural mathematical connection between the AC and fundamental problems complexity theory, won’t someone channel for Herr Gödel and say what that connection is?

• Serge Ganachaud permalink
November 3, 2011 3:20 pm

If P=NP, this can’t be proven directly for reasons that resort to physics. So in this case an indirect proof will be required and it will very likely make use of a strong existence axiom such as the axiom of choice and/or of an axiom for some large cardinal.

In case P=NP, then I really have no clue why it’s so hard to prove. This is why I’ve stopped to believe in that hypothesis. Just because a Turing machine exists, it doesn’t mean that it can be run in our world.

• Serge Ganachaud permalink
November 3, 2011 3:21 pm

… sorry I meant P!=NP in the second paragraph. It’s a pity you can’t edit comments. :)

• rjlipton permalink*
November 3, 2011 5:45 pm

John,

Love you comments, as always. I especially like the “In Iowa…” That comment happens in the middle of the movie the “Blues Brothers.”

20. November 4, 2011 9:24 am

John — As P != NP is arithmetic it is not affected by AC. (The integers lie in the constructible universe, in which choice is always possible, regardless of the full Choice Axiom)

• Serge Ganachaud permalink
November 8, 2011 10:26 am

David – You’ve put recursively all the programs that exist in a box called N, whose properties depend only on Peano’s axioms. Now you expect these axioms to tell you something about the programs – something as strong as whether P=NP. But suppose I had ascribed recursively a number to every possible book, and I told you that book number 2^(2^(2^999)) is worth a Nobel Prize. What would be the safest way for you to get the prize: to perform the decoding job or to write the book yourself? And to make things worse, as you know well, proofs are programs too – which means the proof we’re all looking for possesses its own number in N. So obviously, if we stick with PA we won’t find anything…

• November 13, 2011 6:39 pm

Neither PA, nor stronger axioms like ZFC, completely determine the characteristics of the natural numbers. However, there are certain set-theoretic axioms whose only effect is on the larger set system, not the arithmetic they imply. Suppose that AC implied P != NP. Then consider the constructible universe of set theory. In this model, the natural numbers satisfy AC. Furthermore, the natural numbers in this model are the same as the true arithmetic. Hence, assuming AC -> P != NP means that P != NP is true. In other words, P != NP absolutely.

• November 14, 2011 12:57 pm

David, your reply is IMHO an outstandingly lucid and cogent contribution to this thread. Thank you!

What would be your response to the following pair of propositions? (AC) -> (PvsNP is undecidable) and (!AC) -> (P and NP are not defined).

Assuming the truth of both propositions, would you prefer: (1) accept the undecidability of PvsNP so as to retain the AC? or (2) reject the AC and redefine P and NP constructibly in hopes of separating P and NP? or (3)  retain both the AC and the constructible versions of P and NP?

• Serge Ganachaud permalink
November 14, 2011 5:39 pm

Thank you very much David for your neat explanation. I somewhat knew that “arithmetic” implied “absolute”. My remark was about using additional axioms to settle the question rather than change its truth value.

Feasibility being obviously a fuzzy concept, why keep trying to model it by means of the clear-cut class P? My opinion is: either we should build a new fuzzy concept of feasibility, or we should begin to view class P as a fuzzy subset of class NP. After all, isn’t this the way it appears to all of us?

21. December 3, 2011 12:01 am

Need help Prof. Lipton on one problem

I am not able to find literature on solving the problem (I tend to call it as “group knapsac”). Is this problem well known? What algorithm can be used to solve and whether it a polynomial time problem?

Group knapsac problem:

G is a finite group and S\subset G a given finite set of n elements. For a bit string of length n I pick the elements g_i whenever i^th bit is 1 and take the product

q=\prod_{i=1}g_i

Problem: given q find the bit string.

Virendra Sule

22. August 28, 2013 4:55 am

VEAN POR GOOGLE LAS FALACIAS DE KURT GODEL DEL BLOG http://www.sangretroyana blogspot.com y COMPRENDERA PORQUE EL TEOREMA DE INCOMPLETITUD ES FALSO,UN SALUDO JUAN

23. August 30, 2013 5:48 am

HOLA,VEAN POR FAVOR POR GOOGLE LAS FALACIAS DE KURT GODEL Y COMPRENDERAN PORQUE ESTA ERRADO,EL FAMOSO TEOREMA,RUDY RUCKER RECIBIO CIN ESCEPTICISMO MI COMENTARIO,PERO AHORA LO APOYA DESDE SU VENTANA..MEMORIAS DE RUDY RUCKER