Skip to content

Stephenson:Neal:Quicksilver:36:It is the product of five primes. (Gary Thompson)

From the Quicksilver Metaweb.

This page is about Gödel's Incompleteness Theorem

Stephensonia

Not the first wink in the direction of the Golden Braid.

Authored entries

Composites Instead of Monads

Daniel's scheme is suspicously similar to the technique used by Kurt Gödel in his Incompleteness Theorem. And given Daniel Waterhouse's links to computational machinery and later discussions with Leibniz, this is not a coincidence. KurtGodel.jpg
Kurt Gödel
proved fundamental results about
axiomatic systems showing in any
axiomatic mathematical system
there are propositions that cannot
be proved or disproved
within the axioms of the system

Gödel's Theorem states that any sufficiently powerful logical system either: 1. has theorems it cannot prove, or 2. will sometimes come up with false theorems.

He assigned numbers to symbols in a scheme using prime numbers, much like Daniel, thus creating a unique number for every theorem, and turning statements about numbers into numbers. These numbers were then able to be acted upon by the logical system, effectively getting the system to talk about itself. The kicker was his Gödel sentence, a statement in his logical system basically stating, "this theorem is not provable by this system." Since the Gödel sentence was constructed using the logcial system, either the statement is false, (case 2), or unprovable within the system (case 1).

Try Gödel Escher Bach by Hofstadter for an entertaing and enlightening, if potentially difficult, introduction to Minds, Machines, and Gödel.

Gödel, Escher, Bach

Gödel, Escher, Bach: an Eternal Golden Braid is a Pulitzer Prize-winning book by Douglas Hofstadter, first published in 1979 by Basic Books.

At one level, it is a book about how the creative achievements of logician Kurt Gödel, artist M. C. Escher and composer Johann Sebastian Bach interweave. As the author states: "I realized that to me, Gödel and Escher and Bach were only shadows cast in different directions by some central solid essence. I tried to reconstruct the central object, and came up with this book."

At a deeper level, however, the discussion of these three artists is not actually what the book is about. It is used as a device to illuminate the central theme of the book, which Hofstadter states is this: "Do words and thoughts follow formal rules, or do they not?" (In the preface to the twentieth-aniversary edition, Hofstadter laments that his book has been misperceived as a hodge-podge of neat things when it really has a central, organizing theme. He restates that same central theme in this way: "GEB is a very personal attempt to say how it is that animate beings can come out of inanimate matter. What is a self, and how can a self come out of stuff that is as selfless as a stone or a puddle?")

The book takes the form of an interleaving of various narratives. The main chapters alternate with dialogues between imaginary characters, inspired by Lewis Carroll's "What the Tortoise Said to Achilles", which features in the book. In this, Achilles and the Tortoise discuss a paradox related to modus ponens. Hofstadter bases the other dialogues on this one, introducing the Crab and a Genie, among others.

Word play features prominently: the initials of the four main dialog characters are G, C, A, and T -- the base-pairs in DNA. Some puns may be found quite atrocious, but forgivable for the breadth of the connection they make between ideas: "the MagnifiCrab, Indeed" (Bach's Magnificat in D), "SHRDLU, Toy of Man's Designing" (Bach's Jesu, Joy of Man's Desiring), and "Typographical Number Theory", which inevitably reacts explosively when it attempts to make statements about itself, thus "TNT".

TNT is an illustration of Gödel's incompleteness theorem and further analogies for it occur in the book, for example a phonograph which destroys itself by playing a record entitled "I Cannot Be Played on Record Player X". This is an example of a strange loop, a term coined by Hofstadter to describe things which speak about or refer back to themselves, such as Escher's lithograph of two hands drawing each other.

There are other colorful stories about SHRDLU, the Alternative State of the Union, self-engulfing TV screens, canonical form in music. Other topics range from Zeno's paradoxes to sentient ant colonies. A key question asked by the book is "When are two things the same?"

The book has been translated into several languages. Since parts of the book are about language and translation, translating the work itself has resulted in new material and interplay between the translators and Hofstadter; see the French edition for example. Some material regarding this interplay is to be found in Hofstadter's later book Le Ton beau de Marot, which is mainly about translation.

Important publications

Further reading