# The Gödel Letter

Princeton, 20 March 1956

Dear Mr. von Neumann:

With the greatest sorrow I have learned of your illness. The news came to me as quite unexpected. Morgenstern already last summer told me of a bout of weakness you once had, but at that time he thought that this was not of any greater significance. As I hear, in the last months you have undergone a radical treatment and I am happy that this treatment was successful as desired, and that you are now doing better. I hope and wish for you that your condition will soon improve even more and that the newest medical discoveries, if possible, will lead to a complete recovery.

Since you now, as I hear, are feeling stronger, I would like to allow myself to write you about a mathematical problem, of which your opinion would very much interest me: One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let ψ(F,n) be the number of steps the machine requires for this and let φ(n) = maxF ψ(F,n). The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ k ⋅ n. If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n^{2}), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem. Now it seems to me, however, to be completely within the realm of possibility that φ(n) grows that slowly. Since it seems that φ(n) ≥ k ⋅ n is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungsproblem and after all φ(n) ∼ k ⋅ n (or ∼ k ⋅ n^{2}) only means that the number of steps as opposed to trial and error can be reduced from N to log N (or (log N)^{2}). However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.

I do not know if you have heard that “Post’s problem”, whether there are degrees of unsolvability among problems of the form (∃ y) φ(y,x), where φ is recursive, has been solved in the positive sense by a very young man by the name of Richard Friedberg. The solution is very elegant. Unfortunately, Friedberg does not intend to study mathematics, but rather medicine (apparently under the influence of his father). By the way, what do you think of the attempts to build the foundations of analysis on ramified type theory, which have recently gained momentum? You are probably aware that Paul Lorenzen has pushed ahead with this approach to the theory of Lebesgue measure. However, I believe that in important parts of analysis non-eliminable impredicative proof methods do appear.

I would be very happy to hear something from you personally. Please let me know if there is something that I can do for you. With my best greetings and wishes, as well to your wife,

Sincerely yours,

Kurt Gödel

P.S. I heartily congratulate you on the award that the American government has given to you.

### Trackbacks

- Open discussions on an open problem - Jimagine - Information and Society
- Gödel’s Lost Letter and P=NP | Techarama
- Quora
- Godel’s Citizenship Anecdote « jeppost
- Philosophy and Complexity theory « saranneti
- Giving Some Thanks Around the Globe « Gödel’s Lost Letter and P=NP
- John Nash’s Letter to the NSA « Turing's Invisible Hand
- Nash beats Gödel: On the history of complexity and cryptography « Antonio E. Porreca
- Nash’s beautiful mind pre-empted million-dollar puzzle | Journal of Technology and Economic Development | Future Technology | Green Technology | Military Technology | Business | Trading | Finance | Computer | Robots | Entertainment | Games | GPS | S
- techtings» Nash’s beautiful mind pre-empted million-dollar puzzle
- A Fascinating Letter, continued « Random Walks
- Assorted Links (Theory) | David Cerezo Sánchez
- The origin of the terms "efficient" and "feasible" computation/algorithm | MoVn - Linux Ubuntu Center
- How Good Is Your I-magination? « Gödel’s Lost Letter and P=NP
- John Nash’s Letter to the NSA « A Naive Gardener
- Quora
- John Nash’s Letter to the NSA | onelastpage
- Godel and Gödel: Wine and science « Vintage Direct
- Passeando no Canadá
- Tại sao vấn đề P vs NP khó vậy ? « ZetaMu
- The curious case of P = NP and NP-Completeness | rvalue
- microsoft silicon valley TCS research lab shuts down— easy come, easy go | Turing Machine
- John Nash, Cryptography, and Computational Complexity |
- chessprogramming - Mathematician - SnapBuzz

I am curious about the lower bound result mentioned in the letter:

“it seems that φ(n) ≥ k ⋅ n is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungsproblem”.

Is it an easy result ? Has a proof sketch been found in the margin of Gödel’s notebook?

Was it rediscovered independently; does it follow from a result published thereafter ?

All right, I think I can half-answer my own question (but further comments are still very welcome) : there is a lower bound on the complexity of predicate calculus in a little-known letter by Steve Cook to the STOC’71 program committee.

A proof of the claim φ(n) ≥ kn is given in my paper “On Gödel’s theorems on lengths of proofs II: Lower bounds for recognizing k symbol provability”, in Feasible Mathematics II, P. Clote and J. Remmel (eds), Birkhauser, 1995, pp. 57-90. The paper is also on my web page.

The proof uses a diagonalization argument, so perhaps it is similar to the proof that Godel had in mind.

As I remember, this letter was originally written in German and a rather difficult translation was arranged by Mike Sipser. If you happen to know more details about this, it would be nice to mention them in the post.

Perhaps Mike Sipser should have arranged for an easier translation.

The letter was indeed originally written in German. Mike Sipser’s translation can be found in “The History and the Status of the P versus NP Question”, in the 24th STOC proceedings, 1992, pp. 603-618. This also contains a number of other historical quotes.

Peter Clote also made a translation to English, which can be found in the book “Arithmetic, Proof Theory and Computational Complexity”, P. Clote and J. Krajicek, eds., Oxford Univ. Press, 1993.

Sam, thanks. That reference let me find Mike Sipser’s paper:

http://www.seas.harvard.edu/courses/cs121/handouts/sipser-pvsnp.pdf

According to the paper, the translation in it was done by Soren Istrail and Arthur S. Wensinger.

Footnote 14 of the translation contains a mistake. It sais:

“Gödel uses the English word ‘Analysis’ here, not the German term ‘Analytik’.”

Istrail and Wensinger (or whoever did the translation) overlook that the German technical term for “analysis” is “Analyis”, not “Analytik”. “Analytik” doesn’t mean the mathematical field of analyis, but the philosophical field of analytics. (Also, it may be used in chemistry, meaning “chemical analysis”.)

Unfortunately, I misspelled the word: “Analysis” is right (instead of “Analyis”). Sometimes, some words don’t want to be typed ;)

No one has said, that this is something of a beautiful letter. It is one of the only pieces of non-mathematical writing I have ever read of Godel’s. It moves me because I recently read a biography of Von Neumann by William Poundstone, who describes this period, when V.N. spent his last year in a hospital, dying from cancer he developed as a result of his work on the atomic bomb. According to Poundstone, Von Neumann was only periodically lucid during these last months, and I wonder if he was able to form a response. My impression from the biography is that this would have been difficult.

Hunter, All:

This is indeed a beautifully written letter. Thanks for pointing this out. You have contributed to the spiritual forces of good in this world.

It is a scandal, in my view, that more people do not know about Gödel’s non-technical writings. Everything I have read is simple, smooth, and beautiful. He wrote many, many letters. Obviously translations are a problem but any reputable scholar would have a hard time botching the essence–the kernel– of any idea or concept posited by Kurt Gödel. Note that many, many letters were originally written in English so one need not fret about alternate translations and/or meanings of words. Nor should one worry that there is not enough material. Prof. Gödel was a kind man and he left us with many wondrous items.

That said, I simply wish to acquaint you with two possibly helpful facts:

1. Gödel’s papers are available for anyone (with proper documentation) to see and read. Simply go to the rare books section of Princeton’s Firestone Library and inquire about the “formal procedure”. Soon you will be sitting with God in full view. Sadly, the non-English writings are not presently accessible to many, but there is more than enough to keep you occupied, and happily so,– probably with a huge smile on your face. These papers are a pleasure to read. Period.

2. Hao Wang wrote a few books on Gödel based, in part, on a series of conversations with him at the Institute. Sadly, Wang mixes up his own ideas with those of Gödel’s instead of simply reconstructing Gödel’s views for all to study and cherish. Wang thought it wise NOT to tape record these sessions, lest Gödel become reticent. But key phrases do exist, intact, and a random pick of any will likely suffice for all but the most depraved among us. Moreover, in one of Wang’s books portions of some truly extraordinary translated letters appear–letters written by Gödel to his mother addressing the wildly emotional issue of The Afterlife. Around 1960 Gödel’s mother wrote him and asked if they might see each other again, in another world.

In a series of responses, spread over a few letters, Gödel presents what he claims to be a scientific argument for the existence of The Afterlife. In principle, essentially any child can understand the argument. No scientific training is required — it is self-contained.

Philosophers and scientists have made fun of Gödel’s argument. Smullyan told me that, logically, the argument is ridiculous.

Fine. Great. Wonderful. I am not that quick to judge. More importantly, it is unfortunate that Raymond, and others (who write, and write and write and write their OWN material), did not, do not, and will not state the obvious: Gödel’s letters about The Afterlife are some of the most fantastic, awe-inspiring pieces of writing extent. They will live for a hundred billion years, minimum. And that is an extremely small number, as everyone (here) knows.

Please look into it and decide for yourselves. If you come within one trillionth of my point of view you might go the tiny extra step and ask yourself why nobody told you about them and/or why they are not easily available–available as easily as this website is. Or at minimum, known about, widely, in terms of their “existence” along with a formal procedure for locating them.

Last banal words from Peter Tennenbaum about fine writing: The original preface and introduction to Errett Bishop’s book on Constructive Analysis are the clearest, most beautiful, and eloquent examples of modern English prose I have ever seen. My late father, who sought to film Bishop and Gödel conversing about the foundations of mathematics (apparently a venture of scant interest to mathematicians at the time) strove to make Errett’s prose required reading for every high school student in America. As with Gödel’s writings, Bishop’s will live on and on and on with an intrinsic value that can only increase strictly monotonically as a function of time as time, in the conventional sense of “time”.

Who among us/you/them would or COULD venture to disagree?

Peter Tennenbaum July 24, 2010 (written quickly and under “some” duress… )

Let me add to Peter Tennenbaum’s list 1 and 2 of Gödel sources:

3. Volumes I-V of Gödel’s Collected Works, edited by Sol Feferman et al and published by Oxford University Press.

As Peter says, much of what Gödel wrote was in English. However in his early years he of course wrote in German. For his German writings the Collection gives the German original and its English translation on facing pages for easy comparison.

The Collection is further supplemented by commentary from experts in the field.

Besides his published works the Collection also includes much of his professional correspondence.

I would like to heartily second your recommendation of the books by Hao Wang. It is true that Wang often used Gödel’s ideas as a springboard for his own, but at the same time he had deep respect for Gödel and as I recall he was quite careful about separating his own ideas from those of Gödel. It is a shame that Wang’s books are not more widely known. (I myself have explored both Wang’s and Gödel’s ideas about objectivity in an essay at http://books.stpeter.im/rand/objectivity.html — which I hope shows proper respect for both of them.)

Peter Saint-Andre

Thanks you for the interesting comment. Where could I find a copy of the Afterlife? Many thanks again.

I read this interesting anecdote about Godel’s naturalization exam

http://1372721354610204262-a-jeffreykegler-com-s-sites.googlegroups.com/a/jeffreykegler.com/morgenstern-document/Home/files/Morgenstern_onGoedelcitizenship.pdf?attachauth=ANoY7cpaqR_XkUFnQcIvBKgXk24oRP1usrvvz7kqy1Wsfxu6ggfsxibc5WiIuIszL0765aiqBee8jLhT42K3kPfFpJbS6Kjo9352xk0mnKxrcCm6hJFaTna-kwhQ1sDr0RL_dB2RvViuSRblmpe_o3zt7KQz9EV5GXz0jI7A6oicsHfriDoPLaW_Q2YYV_9E2ws7aJQHf0903YS5mQ2KytIB6ELu3JTn1OlHSlLdrA-WuP40sTvT5Utd2UPTuFdDwXQCGh1nGlHR&attredirects=1

I am curious what could be the contradiction that was worrying him so much? Amazingly, his extremely logic seeking mind was seeing contradictions everywhere.

I believe the specific Hao Wang book to which Dr. Tennenbaum refers above is,

A Logical Journey(excerpts from the letters to his mother begin on pg 104).Beautiful letter from a long time ago. Its amazing to get such a glimpse into such a sharp mind.

I simply wanted to say something that has seldom, if ever, appeared in print–even as a comment on the Web. The only proviso, of course, is that I write this as someone who is not an expert on all the books and, obviously, I have not read every comment on every blog and/or website.

My “new” comment:

Professor Godel had the most amazing voice of ANYONE that I have every met. I am now 54 years old and have spent my life around thousands of people, included many of the top people in math in physics of the last century. I also have ten years of psychoanalytical training, so I know “something” about “affect” and what to listen for.

Professor Godel’s voice, over the phone, and in person, was the calmest, sweetest, and most enjoyable voice that I have EVER heard. As my [now[ late-father pointed out, Godel was devoid of “hyseria” — there was not even a hint of it in his affect, in his voice.

Hao Wang considered taping his conversations with Godel but decided against it for fear of disturbing Godel in some way. This was possibly a wise move. I cannot say much about that, now. What I know for sure, and what I commented on previously (if memory serves me correctly!) is that my father, who knew Godel probably better than anyone else, certainly after 1965, and who often spoke with him every night, at 8 PM (a joke between them, because if you turn 8 by 90 degrees it looks like the infinity sign) wanted to film Godel talking with children and others, including Errett Bishop, another person with a remarkable voice AND sense of humor.

Godel had a fantastic sense of humor, something else that is not written about or talked about much.

It is a shame, really. As Verena Dyson wrote (commenting, I think, about all the crazy rumors and gossip about Godel): simply leave the man (who is now dead) alone! (in terms of all this banal and sometimes vicious gossip. He was a sweet and kind man. This is something that impressed ME more than his mind although his voice is more unusual than being kind — and Godel’s voice was simply nothing that existed in this world. He spoke from another world.

Almost everyone has a perfect mind at conception and/or birth. What happens later, however, is another matter entirely!

Best Wishes to all decent people,

Peter Tennenbaum

http://www.dynastring.com

http://www.cancerdisaster.org

I think degrading or poking fun at Godel is mean-spirited and uncivil.

However, he is dead and no longer capable of being hurt by these comments. So given the choice I’d rather people take out their vitriol on a brilliant, nice but dead man like Godel rather than on even the most awful living person.

There is never any excuse to increase overall suffering and sadly human nature inclines us to lash out when angry, upset, defensive etc..

To clarify it really doesn’t matter how nice Godel was. Pain is pain whether experienced by a serial killer or a saint. Regretably we must sometimes inflict pain for the greater good.

The only reason we react so strongly to mean comments about nice people is because we lack the temptation (and thus empathy) to do it ourselves.

I made a terrible spelling error above and readers might not understand the intended thought/meaning.

I meant to write that Godel’s voice had no “hysteria” in it. My error, according to Godel’s general views about the mind, indicates that I have some hysteria! True, but I also need new glasses, too.

The regrettably late John Wheeler might not have agreed in re: KG’s sweetness of nature, as he reports having been “thrown out” (figuratively, surely) of Gödel’s office for suggesting similarities between Incompleteness and Heisenberg’s Undecidability … (He chalked it up to Gödel having been “brainwashed” by Einstein).

Objectively, Gödel was right to throw away these superficial similarities between logic incompletness and quantum incompletness. Indeed, there are more tight links between logic undecidability and incompletness in … theory of Relativity. Was he conscious of these tight links ? Is it the reason why he was so interested in Relativity and close to Einstein ?

Dear Rick P.:

Surely, everyone can become less than gracious, if pressed–even unconsciously.

I wonder whether YOU believe that are any serious, interesting (non-superficial) connections between Godel’s theorem and Heisenberg’s so-called “principle”. If not, can you suggest another source other than Wheeler? My understanding is that Gödel’s theorem proves that mathematics is inexhaustible.

I know little about Heisenberg’s work but it would appear, from the outside, that physics stops there. It constitutes a kind of boundary, completely at odds, philosophically, with the positive interpretation of Gödel’s theorem. It is NOW well known that Gödel was extremely upset at how his work was received–the negative and erroneous interpretation, spread far and wide, that somehow certain mathematical questions would NEVER be resolved–the propaganda that he somehow proved this.

There are clear and obvious reasons why Gödel would be offended by such talk, especially coming from an educated person. Further, I rather doubt he believed that Heisenberg’s “Undecidability” (sic) would stand the test of time. We shall see… well “us” in the broad sense of history although I don’t know enough to say whether or not it is possible that the uncertainty principle could be shown false any day now, in OUR lifetimes.

Most everyone, at some point, is “regrettably late” in one way or another; at least so far. Hopefully this too will change!

Happy New Year to All,

Peter Tennenbaum

I agree, we’re all human. The fact that I said “Undecidability” rather than “Uncertainty” tends to demonstrate that. The anecdote simply happens (perhaps unfortunately) to be one of however many that KG will in part be remembered by. Maybe Wheeler was baiting him, consciously or not; that was during the height of the Bohr-Einstein ongoing debate and Wheeler was a protégé of Bohr. You just have to love high-class gossip.

Uncertainty implies Incompleteness, Undecidability, Indeterminism. All deal with a point at which understanding becomes slippery. In the case of Uncertainty the point is defined by a trade-off: you need to surrender knowledge about X in order to obtain knowledge about Y. That’s a built-in bound to knowledge. In the case of Incompleteness you find that no mathematical system is able to validate itself. Extrapolating that beyond mathematics (which reputable physicists have done: Lee Smolin comes to mind) it occurs to one that as constituents of this universe we may never be able to see it whole simply because we are constituents. Might there be a deeper connection between these two already profound observations? You don’t need to be a theoretical nuclear scientist to wonder about all that, although in Wheeler’s case it probably didn’t hurt.

Anyway, here’s one reasonably non-superficial tracking of a proposed connection:

http://arxiv.com/abs/quant-ph/0402197

what an odd relationship scientists have:

“Mr X, sorry you are dying. In the meantime, could you help me solve this mathematical problem I’m having difficulty with:

……………….

………………[100 lines later….]

So, hope you can help at your earliest (at the least before your imminent demise)! It would be most useful. Regards to your wife. (give her my number, will you).

Best,

Signed, Y: another mathematician at fancy institute.

Even though Von Neumann had the reputation of being able to prove whatever he wanted, one may indeed feel disappointed at Gödel’s inhumanly behavior. At least he should have had the intuition that P?NP was perhaps independent of ZFC – just like the continuum hypothesis.

“Inhumanly behavior”? “Odd relationships”?

What has happened to this thread? It appears to have turned decidedly ugly.

Very sad, as it’s a beautiful letter from an exceedingly kind and decent man whose personal life and relationships have been the source of vicious rumors, outright lies, and seething jealousies. I have some right to say this as I had the enormous pleasure of knowing the man.

People have turned this letter and the intention behind it upside down. Godel didn’t need any mathematical help. HE WAS HELPING HIS FRIEND, in his OWN way.

Peter Tennenbaum

Peter Tannenbaum wrote:

“Godel didn’t need any mathematical help. HE WAS HELPING HIS FRIEND, in his OWN way.”

Indeed, this is the best way, positive way to help a friend to recover.

Vailliant warrior prefer not to die quitely in a bed but instead in the battlefield. What a high respect for a friend to give him the opportunity to keep fighting!

Peter’s post and Nasreddin’s post both are outstanding (IMHO).

As von Neumann once wrote to Abraham Flexner (the director of the IAS): “Gödel is absolutely irreplaceable; he is the only mathematician alive about whom I would dare to make this statement.”

The same might perhaps have been said also about von Neumann himself … thus in Gödel’s letter we see one great mind reaching out to another.

hey….apologies to all and the late great Mr G!

just trying to be a bit comedic. ….you have to admit: my sendup IS a rather funny interpretation viewed in isolation. (though, out of context).

I acknowledge too that I was being inappropriately provocative in my preceding comment. I apologise for the wrong adjective that I used.

With hindsight, I understand now that Gödel’s “last letter” was rather an instance of procrastination. He had probably been thinking of submitting this problem to his friend for a long time, when he sadly realised that he had to send the letter as soon as possible.

Now, just for the pleasure of the comparison – and I hope it’s not out of place here: Fermat gave us his wonderful problem because of a lack of space – the narrow margin in his copy of Euclid’s Elements – whereas Gödel gave us this one as a result of a lack of time. I’m sure that this means something…

Dear Kiers: I often curl up with a good puzzle book when I’m not well. It distracts me from my misery and feelings of time wasted, and is several orders of magnitude better than TV! To have a friend send me an interesting puzzle is just what I need, and I would return the favor. It’s a great opportunity to cement a friendship.

I agree that, in principle, Kiers’ post is quite hilarious. In practice, however, it might be better suited to a situation involving pompous academics (they are essentially everywhere dense now, contrary to the period in question–and if not the period then the people).

In response to Serge, I can say that I very much doubt that lack of time (on Godel’s part) had ANYTHING to do with his letter to Von Neumann. A more reasonable interpretation is that he wanted to give Von Neumann something VERY INTERESTING to think about during a time of great stress, thus helping to relieve the stress. Godel had an extremely subtle and gentle way of helping others. It almost always took the form of attempting to direct their minds to something interesting, fruitful, and/or enjoyable.

From what little I know, there is a long history of Godel asking questions that he already knew the answers to. According to my late father, one could easily glean this from a close examination of the questions (or, even better, to a series of questions) as one could not possible pose them without a deep sense of where the answers would be found. Here, Godel may NOT have known the answers in terms of precise technical solutions, as he probably arrived at his conclusions via philosophical arguments–applying his extraordinary philosophical viewpoint–something that served him extremely well in his own technical work.

Paul Cohen is in print as saying that his work on the continuum hypothesis was borne from a philosophical idea–and the rest was simply formalities. I am hardly an expert here but I’m sure there are a host of similar examples. Indeed, it appears that Godel himself discovered forcing decades before Cohen. This may well explain Godel was so confident that Cohen’s proof was correct at a time when Cohen was in considerable distress that some mistake might be found in his argument (see, for example, the correspondence between Cohen and Godel; I have read these letters in Godel’s Nachlass at Princeton University but, if I am not mistaken, part of the “dialog” appear in the official Godel volume devoted to correspondence).

Entscheidungsproblem is supposed to be not generally solvable, wikipedia sends us to Turing-Church theorem. ‘Turing in 1936–37. Church proved that there is no computable function which decides for two given λ calculus expressions whether they are equivalent or not’.

And how it can work together with Stevene Cook’s words below?

‘it [fact that P=NP in case proven] would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.’

Is there any contradiction? By the way is there any works oriented on isomorphism of any mathematical axiomatic basis and circuit sat?

Can anybody give link or send me Cook’s paper ‘Can computers routinely discover mathematical proofs?’. It’s hard to find full version of it in the net.

JSTOR apparently has it:

http://www.jstor.org/stable/986492

Thus it should be accessible through any of the major university libraries.

Info derived from putting ‘Can computers routinely discover mathematical proofs?’ into google.

Fascinating post followed by an equally fascinating comment thread!!