Kurt Gödel came into our world one hundred years ago today.
Gödel's incompleteness theorems changed the way we think about
mathematics.We reprint the translation of the now famous letter he wrote fifty years ago to von Neumann which was rediscovered in 1988. This letter describes something close to the P versus NP problem years before the field Computational Complexity even had its name. SIGACT and EATCS jointly sponsor a prize named after Gödel because of the 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 ⋅ n2), 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 ⋅ n2) 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).
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.
[The text is taken from this page where you can also find the original German text and acknowledgments. John von Neumann, who received the Presidential Medal of Freedom in 1956, had cancer at the time of the letter and passed away in 1957.]
Hmmm, it seems that the
ReplyDeleteScott's comment shows how a fan can read beyond what other's could from the same text:) This is a pretty powerful phenomenon especially with current media technology. Nothing wrong about it. It's indeed needed because there is a fan hierarchy and people can really understand some stuff.
ReplyDeleteDoes anybody else find it difficult talking about Godel's *completeness* theorem without people mishearing you?
ReplyDelete"Yeah, the proof kind of reminded me of the structure of Godel's completeness theorem"... "[some BS about the incompleteness theorem]"... "Uh, I said completeness." ... "What?"
But if G�del was correct, then the fan hierarchy would collapse to its first level.
ReplyDelete"But if G�del was correct, then the fan hierarchy would collapse to its first level."
ReplyDeleteThe fan hierarchy can help in understanding the correctness and then after couple of such instances the hierarchy might not be relevant (which means yes collapse but I don't prefer to use the word collapse:)).
It is indeed impressive that Godel in this short letter had the kernel of the key questions of complexity and whether SAT is in P a decade before anyone else would pose them. However, we shouldn't lose sight of the fact that this letter didn't play any role in the development of the field. Was it the lack of anyone else he would want to talk to about it after von Neumann's passing? Godel's significant role in the field was 25 years earlier.
ReplyDeleteWas it the lack of anyone else he would want to talk to about it after von Neumann's passing?
ReplyDeleteI think that it was Goedel's personality, and his nature not to say anything that he couldn't defend. The man was a genius, but wasn't recognized as much, because of his poor speaking skills. I have heard that even when he revealed the proof of his incompleteness theorems, he did so in a very low-key fashion, and it was a couple of years before people realized their significance.
Here are excerpts from a little-known 1955 essay by von Neumann, on the topic of -- global warming!
ReplyDeleteVon Neumann and Godel were both quite far ahead of their time, eh?
@inCollection{vonNeumann:55, author = {J. von Neumann}, title = {Can we survive technology?}, booktitle = {The Fabulous Future: America in 1980}, publisher = {E. P. Dutton {\&} Company},year = 1955, pages = {33--48}, jasnote = {von Neumann quote 1: "All major weather phenomena \ldots are ultimately controlled by the solar energy that falls on the earth. \ldots "The carbon dioxide released into the atomosphere by industry's burning of coal and oil---more than half of it during the last generation---may have changed the atomosphere's composition sufficiently to account for a general warming of the world by about degree Fahrenheit. \ldots Intervention in atmospheric and climatic matters will come in a few decades, and will unfold on a scale difficult to imagine at present. \ldots Such actions would be more directly and truly worldwide than recent, or presumably, future wars, or the economy at any time. \ldots All this will merge each nation's affairs with those of every other, more thoroughly than the threat of a nuclear or any other war would have done. \ldots What safeguard remains? Apparently only day-to-day---or perhaps year-to-year---opportunistic measures, a long sequence of small, correct decisions. And this is not surprising. After all, the crisis is due to the rapidity of progress, to the probable further acceleration thereof, and to the reaching of certain critical relationships. Specifically, the effects that we are now beginning to produce are of the same order of magnitude as ``the great globe itself.'' Indeed, they affect the earth as an entity. Hence further acceleration can no longer be absorbed as in the past by an extension of the area of operations. \ldots The most hopeful answer is that the human species has been subjected to similar tests before, and seems to have a congenital ability to come through, after varying amounts of trouble." },}
ReplyDeleteHowever, we shouldn't lose sight of the fact that this letter didn't play any role in the development of the field.
WHY this is true?
I came across a neat site on Kurt Gödel called Simply Gödel at www.SimplyGödel.com
ReplyDeleteThe link to Steve Rudich's site doesn't work any more.
ReplyDelete