An Incomplete Birthday

James Monroe was born this day in 1758. Portuguese painter Jose Malhoa was born in 1855. The lesser brother, Lionel Barrymore was born in 1878. Blues great Charlie Patton was born in 1891. Romance novelist and despot Saddam Hussein was born in 1937. And Bruno Kirby was born in 1949.

The great Harper Lee is 87 today. On even the most impressive days, she would be the person of the day—just not today. Not totally unreasonable conservative James Baker is 83. Novelist Terry Pratchett is 65. Once funny comedian Jay Leno is 63. And actor Penelope Cruz is 39.

But the day belongs to mathematician Kurt Godel who was born in 1906. When I was young, I worked very hard to understand his incompleteness theorems. These basically said that any axiomatic system of sufficient complexity was necessarily incomplete. Since the time of Euclid, mathematicians had hoped they could state a few postulates and create a complete system based upon this—know everything about the system. Not true, showed Godel. Here is Rudy Rucker’s non-mathematical proof from his book Infinity and the Mind:

The proof of Godel’s Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:

1. Someone introduces Godel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
2. Godel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
3. Smiling a little, Godel writes out the following sentence: “The machine constructed on the basis of the program P(UTM) will never say that this sentence is true.” Call this sentence G for Godel. Note that G is equivalent to: “UTM will never say G is true.”
4. Now Godel laughs his high laugh and asks UTM whether G is true or not.
5. If UTM says G is true, then “UTM will never say G is true” is false. If “UTM will never say G is true” is false, then G is false (since G = “UTM will never say G is true”). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
6. We have established that UTM will never say G is true. So “UTM will never say G is true” is in fact a true statement. So G is true (since G = “UTM will never say G is true”). “I know a truth that UTM can never utter,” Godel says. “I know that G is true. UTM is not truly universal.”

Of course, Godel was a nut. Many mathematicians are profoundly introverted, living largely in an unseen word of ideas. Even with my little brain, I feel very much a kinship in this way and I regret having studied physics rather than math. Regardless, I’m not crazy. Godel starved himself after his wife died because he would only trust food she had made. It is very sad. But he left us a great legacy.

Happy birthday Kurt Godel!

This entry was posted in Uncategorized by Frank Moraes. Bookmark the permalink.