Godel, Escher, Bach: An Eternal Golden Braid

---
The proof of Goedel'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 Goedel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.

2. Goedel 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, Goedel 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 Goedel. Note that G is equivalent to: "UTM will never say G is true."

4. Now Goedel 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").

7. "I know a truth that UTM can never utter," Goedel says. "I know that G is true. UTM is not truly universal."

Think about it - it grows on you ...

With his great mathematical and logical genius, Goedel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics ...

Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth ... But, paradoxically, to understand Goedel's proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Goedel's name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.
---

This is the kind of mental freedom you will gain by reading this book. Highly recommended.


One of the biggest influences in my life, and a classic.   August 25, 2001
Gerald J. Nora
12 out of 13 found this review helpful

Douglas Hofstadter uses the art of M.C. Escher, the music of J.S. Bach, and Kurt Goedel's mathematics as the centerpieces for a magnificent inquiry into the nature of the mind. Along the way you will encounter Bertrand Russel, Carroll Lewis, particle physics, molecular biology, Magritte's paintings, and Zen koans. These are all used to probe recursion and the mystery of how we form thoughts. But the list of topics alone is not what makes this book great, it's the playful, joyful sense that characterize's Hofstadter's treatment of this. This sense of wonder is critical, as without it this highly challenging book would be very frustrating. The book's style itself is based on Bach's canons, and the chapters are interspersed with dialogues between the Tortois and the Hare, in the style of Carroll's Alice in Wonderland. The result is an artistic as well as scientific or philisophical masterpiece. I am currently a triple-major in molecular biology, physics, and philosophy, and much of my curriculum has been influenced by the beauty of Hofstadter's book. This will go down as one of the 20th Century's bests books.