Goedel Escher Bach

Gödel Escher Bach, an Eternal Golden Braid by DouglasHofstadter

"Besides being a profound and entertaining meditation on human thought and creativity, this book looks at the surprising points of contact between the music of Bach, the artwork of Escher, and the mathematics of Gödel. It also looks at the prospects for computers and artificial intelligence (AI) for mimicking human thought. For the general reader and the computer techie alike, this book still sets a standard for thinking about the future of computers and their relation to the way we think." -- Amazon review

Distinctions between o and ö -- What's in a name :

: Hint: It's "Gödel" or "Goedel" (if you cannot type "ö"), not "Godel". Strangely it is spelled "Godel" once on Hofstadter's homepage; it is also spelled "Gödel" and "Goedel" on the same page. (sic) Seems like Doug didn't get his xmodmap right...

This book explores the relationship between music, art, and mathematics. It compares the fugues of JohannSebastianBach to the art of MauritsCorneliusEscher and the math of KurtGoedel.

I thought that it explored human thought and ArtificialIntelligence through the themes of music, art and mathematics.

I was given the 20-year edition for Christmas, which has a new introduction from Hofstadter. Slightly out of context, here is what he says:

: "In a word, GEB is a very personal attempt to say how it is that animate beings can come out of inanimate matter."

I've read the first half of the book. My interpretation of the book so far is that it primarily focuses on a slow but mentally engaging metaphorical buildup to the concepts of GoedelsIncompletenessTheorem, with a lot of digressions about infinity in general, isomorphic systems and structures, and layers of abstraction. -- SteveHowell

Which shows that you've read half the book :) The ultimate aim of the book is to continue the buildup through the Incompleteness theorem, describing tangled hierarchies and strange loops, and finally show how that relates to his conviction that human-level consciousness/strong AI can appear in a machine. -- Jeff Bay

The mathematician JeanYvesGirard characterized this book as a "masterpiece of vulgarity". See JeanYvesGirardOnGoedelEscherBach.

Includes a very rudimentary programming language designed, IIRC, to demonstrate GeorgCantor's diagonal method. See BloopFloopAndGloop and CantorsProof.

This is an astounding book using dialogues interspersed with the prose and extensive illustration. It won the 1980 Pulitzer after it was published in 1979. The author's focus is the role of self-referencing in cognitive and consciousness and he deftly weaves the tale through the afore-mentioned artforms. Look for many layers of self-referencing in the book as the author has embedded multiple levels of interpretative meaning throughout. Worth reading more than once for anyone who enjoys thinking about the world of ideas, enjoys interdisciplinary play, or is interested in speculation about the nature of intelligence and consciousness.

See DouglasHofstadter for a list of his other books with ISBN numbers.

Evidence on GoedelEscherBach winning the Pulitzer award may be found at

Here is the text, cited from http://www.pulitzer.org, that describes the Pulitzers that are awarded for books:

While the journalism process goes forward, shipments of books totaling some 800 titles are being sent to five letters juries for their judging in these categories:

For distinguished fiction by an American author, preferably dealing with American life.
For a distinguished book upon the history of the United States.
For a distinguished biography or autobiography by an American author.
For a distinguished volume of original verse by an American author.
For a distinguished book of non-fiction by an American author that is not eligible for consideration in any other category.

Maybe it counted as journalism because of the dialogues?

Someone on TheismVsAtheism suggested GoedelEscherBach as an explanation of what happens inside an atheists brain when, logic comes up empty, or when self referential questions lead to the inevitable break down of logical system. This page has given me no insight on this aspect of the book, so I'll add it to my reading list, but it will be some months before I get to it. Can anyone comment on this aspect of the book to whet my appetite? -- GregVaughn

GoedelEscherBach explores the notion of "undecidable propositions", that any interestingly powerful formal system is either a) incomplete, meaning that certain "truths" (valid theorems) are not provable from within the system, or b) inconsistent, meaning that at least one theorem can be simultaneously proved both true and false. Such theorems often leak as axioms. Thus, for example, EuclidOfAlexandria declared that parallel lines never meet. He declared this as an axiom because he was (to paraphrase his own words) unable to prove it as a theorem. NonEuclidean geometry was born from the effort to assume the converse and find the supposed contradiction. The surprise was that instead of a contradiction, a new and parallel geometry was discovered. I'm carefully resisting the temptation to further the TheismVsAtheism page, but an obvious connection to GoedelEscherBach is to view the existence or nature of God as an axiom, undecidable within a given framework (such as our lives). We may choose to live in a universe without a God, or we may choose to live in a universe with a God, and if we choose to live with a God, we may choose the nature of that God (the technical term for such choices is a "theology"). None of these is "provable", and hence the futility of arguing about it. Euclidean and NonEuclidean geometries each "work". Nonetheless, *within* the context of a given theology (including "atheism", which itself has many shades of meaning), one *can* make deterministic and provable statements about that theology, just as one can make specific statements about the truth or falsity of a particular putative theorem. For example, one can correctly identify internal inconsistencies among multiple assertions about the nature of the God (or lack thereof) contemplated by the theology. Whether to then describe one or more of those assertions as "wrong" depends on the theology itself. I tend to abhor such inconsistency, and so I avoid it. But many prefer to simply live with it. -- TomStambaugh

Interjection: So long as we are working logically, though, don't we have "from a contradiction, anything follows?" As in, an inconsistent system is complete only by having everything. That's not something any formal system can live with.

Thank you for the summary, Tom. I'm still working on wrapping my brain around the idea of "undecidable proposition". If I understand the definition of it, then apparently the author believes that only uninteresting systems of thought can be complete. I don't think that's something I can swallow. I'm also interested in your statement that you abhor inconsistency. Does that imply that you're satisfied with incompleteness? -- GregVaughn

The phrase "interestingly powerful" is my own, not DouglasHofstadter's. The reference is not to "systems of thought", but instead to formal systems, in a mathematical sense. Whether any of us can "swallow" it is immaterial; Goedel proved, mathematically, that it is a fact of formal systems. The technical definition that I paraphrased as "interestingly powerful" is carefully and rigorously presented by both Goedel and DouglasHofstadter; it's an important aspect of understanding the GoedelsTheorem. The implication, in philosophical terms, is that we must always choose between knowing that there are truth's that cannot be proven (incompleteness) or knowing that there are statements that are both true and false, at the same time (inconsistency). My aversion to inconsistency leads me to explore different or deeper understandings (often of enclosing systems). For example, when I am confronted with empirical evidence that an entity (lets use a photon as an example) is both a particle and a wave, the apparent inconsistency leads me to become curious about an enclosing understanding that unifies the two sets of observations. Similarly, when I am faced with a paradox such as proving the truth or falsity of the assertion: "God can create another God" ("No, there can only be one omnipotent being, by construction.", "Yes, God can do anything God chooses"), I am drawn to seek a different understanding of God (or the meaning of "create") as a way of resolving the apparent paradox. And yes, I generally prefer incompleteness to inconsistency; I'd rather say "I don't know" than "Well, yes and no". -- TomStambaugh

Another interjection: I think those little things Aquinas resolved, in a perfectly fine way, by pointing out that phrases like "another God" and "stone so heavy God can't lift it" are inconsistent with God's definition and so meaningless. In short, God can't make them any more than he can make uioqsry. This is kind of like saying he is constrained by consistency.

Aha! Thanks for the clarification. Then I do agree on the incompleteness vs inconsistent issue. The book is sounding more and more interesting. -- GregVaughn

Greg, it looks like I need to loan you another book. :-)

I would say that I'm definitely satisfied with incompleteness. One of the reasons I've stayed out of most of the recent theological discussions - even though I'm an evangelical Christian - is that they seem wrongly focused on "proving" this or that, or on answering every question. I know I'm abusing Goedel's math a bit by stretching it into an unintended (and not entirely applicable) domain, but I think many of the questions we have about God fall into the category of true statements that cannot be proved within our system (nature). And I think when we are unwilling to say "I don't know" or even "We can't know" we get into trouble. -- GlennVanderburg

[You are abusing it more than a little. Issues of faith do not map at all well onto this idea. If I have an axiomatic system with an unprovable but true statement in it, this is quite different from a statement that *can't even be made in the system*. Theology can easily lead you to questions that are not knowable in any consistent logical system whatsoever. The statement "We can't know" is exactly correct in some cases - what you believe about the statement then is a pure matter of faith.]

Oh, and just to keep us focused on software, GoedelEscherBach contains a great derivation showing that the HaltingProblem is fundamentally a restatement of GoedelsTheorem. Hence the futility of attempting to design a BigCase tool that will "prove" that a given piece of software "works" (or that will generate a provably correct piece of software) -- TomStambaugh

: Quibble. GoedelsTheorem can be used to show the futility of a system proving certain things about itself (or systems that are powerful enough to implement itself). One can still use a more powerful system (with more possible states) to prove statements about a less powerful system. Computer Science proofs often use infinite TuringMachines rather than real-world limited systems.
: For a trivial example, consider the HaltingTheorem for all 3-byte programs in 6502 machine language starting at address 0x1000. (For simplicity, consider a machine where only the three bytes are real memory, and all other addresses are wired to produce an immediate halt on access.) One can use a modern PC and try all 16,777,216 possible programs and store the results (halt/no-halt). (One can detect loops by comparing the complete machine state to all prior states for the run. Three bytes allows simple finite loops like "increment X register; branch to start if non-zero".)
: For a less-trivial example, there has been some research in writing provable programs for tiny embedded devices (perhaps with 1K of ROM and 32 bytes of RAM). One uses a much more powerful system for the proof. In principle, GoedelsIncompletenessTheorem would not prohibit a machine with X+n bytes of storage proving all true statements about a machine with X bytes of storage. (The X+n byte system is a superset of the X-byte system. I suspect that n could be as small as 1. Probably not, but it can be O(1).) In practice, orders of magnitude more storage and speed may be needed for a long time. Still, many people would be happy if they could prove 64-kilobyte programs correct using a 100-megabyte proof system. (Consider a pacemaker control system as described in XpChallengePaceMakers.)
: Finally, even if not all valid programs pass such a validator, one could use the validator as a kind of "lint" tool. For certain critical systems one might only accept a validated program, even though a non-validatable program might be correct. The principle is similar to insisting that one's C code compiles without warnings, even if the warning-triggering code really is correct. Perhaps a future ProvableXp? methodology will make some basic proofs (halting, no language-undefined behavior, no undeclared side effects, etc.) a UnitTest requirement... [Feel free to move all this to a more topical page.]
: Yes, I'm aware of your quibble. But (and I think this is in the spirit of DouglasHofstadter's argument) how do I know (i.e. prove) that the "more powerful" system is itself correct? In more classical terms (I used to know the Latin - {Quis custodiet ipsos custodes} ) -- Who shall guard the guards? I believe one is forced, eventually, to pass the validator itself through the validator, at which point the HaltingTheorem applies. I'm getting a bit lost in the recursion here, but I hope you see my direction. Thanks for your comments. -- TomStambaugh
: Does a system have to be proven correct, to be capable of producing the proof of a lesser system's correctness? -- GRLove
: In fact, a system cannot prove itself both correct and reasonable. -- God

Tom, you're mixing up "proving a given program" and "generating a provable program". In fact, generating a program that does something along with the proof that it indeed does that, is far easier (read: possible as opposed to impossible) than generating the program and then attempting to find the proof. Even in complete systems, where every statement can be proved either true or false, finding a proof is much harder (often in NP or even worse) than generating a proof and verifying it (which is usually in P). To write a program and prove it, you just have to do it simultaneously.

A pretentious and tedious book. I am ashamed to admit how I came to own two copies. (wrote someone on a misnamed page..)

... couldn't agree more. I felt cheated when, having laboured through almost the whole book, Hofstadter finally revealed his basic faith in the mind as an emergent phenomenon. (Whoop-de-doo). I heard that when Hofstadter gave a lecture at Caltech on the subject material, RichardFeynman (who was in the audience) tore him (figuratively) to shreds. Maybe apocryphal, but the thought appeals to me.

Long, but not tedious. I understood as a very gentle (and then long) introduction to the idea that mind can emerge from the layering of (each time more) complex structures. -- GeraldoXexeo

It convinced me that free will is an illusion. -- EricHodges

In what way did this come about?

I knew you were going to say that.

See TheEmperorsNewMind by RogerPenrose, TheMindsIbook by DouglasHofstadter and DanielDennett

CategoryBook