5 ms·

For those interested, Hoffstadter's Godel Escher Bach gives a great introduction into formal systems and Godels incompleteness theorem. Highly recommended.

afthonos 8y ago
I read it cover to cover out of a sense of obligation but came away very disappointed. The Achilles-Turtle-Random Other Creature allegories got very tiresome, and the content took a very long time to get to the point. For anyone interested in the proof, I recommend Gödel’s Proof by Nagel instead. It covers the same material in about a tenth the space. (GEB has other philosophical discourses that are interesting, if only as an example of how people can very reasonably mispredict the future. In Hofstader’s case, he posited that chess would only be played at a human level by an AGI.)
- manifestsilence 8y ago
  I agree that it's way over-long and rambling, but it was my introduction to the topic. Where it really shines is his interesting and controversial thesis that connects Godel's proof with the Church-Turing thesis and other things to form a theory of consciousness as pattern and make the claim that a sufficiently powerful AI is as sentient and meaningful a consciousness as we are. I read Godel's Proof after though, and I agree that it is a far clearer introduction to Godel's theorems.
- et1337 8y ago
  Absolutely agree. GEB constantly tries to prove the cleverness of the author, complete with winks and nudges. It stacks so many unintuitive analogies on top of each other that I spent most of the time trying to recall which real-world concepts they all mapped to. Also, the book is about 98% Gödel and 2% Escher and Bach. Any time it steps outside its wheelhouse of math and into the realm of philosophy or art, you get the distinct sense that it has no idea what it's talking about. Do yourself a favor and just take discrete math 1 and read a few Wikipedia articles instead.
  - mhneu 8y ago
    Do yourself a favor and just take discrete math 1 and read a few Wikipedia articles instead. +100, exactly. I have some familiarity with mathematical logic, and with Bach (though admittedly I'm less familiar with Escher) and I found GEB to be unintuitive at best, and misleading at worst. To be honest, there may not be anything really magic about Goedel's incompleteness theorem once you grasp the core concept, which is: If you encode all proofs into a formal language, you can make a statement that is true but unprovable. (Which is, effectively: "This statement has no proof"). Most of Goedel's work on the incompleteness theorem was on the systematization of proofs, which can be tedious to work through. I found at the time Godel's completeness theorem to be more interesting. Though I never got into model theory or more advanced mathematical logic so, grain of salt.
- westoncb 8y ago
  I found 'Gödel’s Proof' fascinating—surprisingly more so than GEB, which I'd anticipated loving for years before dipping into it (I didn't finish, but the primary reason was loss of interest). It was one of the first things I came across that gave me the sense of something like 'mathematical system architecture'.
- misiti3780 8y ago
  If you still have the energy or interest, try I Am A Strange Loop, he wrote in a number of years after and it seemed more approachable
  - fredgrott 8y ago
    thank you...I just bought it via amazon
- pflats 8y ago
  The New Turing Omnibus has a good chapter on the Incompleteness Theorem; it covers the basics in 5 or 6 pages, if memory serves.
- carlehewitt 8y ago
  Chaitin [2007] presented the following analysis: Godel's proof of inferential undecidability [incompleteness] was too superficial. It didn't get at the real heart of what was going on. It was more tantalizing than anything else. It was not a good reason for something so devastating and fundamental. It was too clever by half. It was too superficial. [It was based on the clever construction] I'm unprovable. So what? This doesn't give any insight how serious the problem is.
raverbashing 8y ago
Yes And GEB's explanation of it is more complete/exact than the one in the article. It is also amazingly mind-twisting. Not the explanation per se, but the theorem. And I think its consequences are under appreciated: no (sufficiently complex) logical system is free from self-contradictions.
- wk_end 8y ago
  I believe that's a misinterpretation of Goedel; it's an incompleteness theorem, not an unsoundness theorem. Incompleteness: there exist true statements that lack proofs Unsoundness: there exist false statements with proofs If I understand all this correctly, what Goedel demonstrated was that a sufficiently complex logical system could self-reference, and from self-reference unprovable (not contradictory) true statements fall out. By reductio ad absurdum any self-contradictory logical system is useless as a logic because everything is provable in it, so one wonders if such systems should even be considered "logical systems".
  - raverbashing 8y ago
    The inconsistency part is the 2nd incompleteness theory. You don't RAA it because you can't prove the system is consistent (because you can't prove the counterexample)
    - wk_end 8y ago
      "Gödel's second incompleteness theorem states no consistent axiomatic system which includes Peano arithmetic can prove its own consistency. Stated more colloquially, any formal system that is interesting enough to formulate its own consistency can prove its own consistency iff it is inconsistent." [1] I believe your position is that "sufficiently complex" == "able to formulate and prove its own consistency"; my position is that such a system would be worthless as a logic, because in such a system you can prove anything. Your second paragraph is inscrutable to me. Are you trying to claim that you can't prove everything with a known inconsistent logic? Are you referring to paraconsistent logics? [1] http://mathworld.wolfram.com/GoedelsSecondIncompletenessTheorem.html http://mathworld.wolfram.com/GoedelsSecondIncompletenessTheo...
DyslexicAtheist 8y ago
obligatory "I am a Strange Loop" reference here for anyone who wants a more polished introduction into the topic from many years later. He wrote GEB when still very young and had time to refine his points in this later book.
- chj 8y ago
  Unfortunately his style sticks.
draw_down 8y ago
I disagree, I find it to be much more along the lines of “hey this thing is sort of like this other thing, isn’t that cool?” and rather impressed with itself. And it’s extremely tedious when it gets to the place of trying to re-derive formal logic. I don’t really understand why people consider it such a classic, I don’t feel I got much from it at all.

afthonos 8y ago

I read it cover to cover out of a sense of obligation but came away very disappointed. The Achilles-Turtle-Random Other Creature allegories got very tiresome, and the content took a very long time to get to the point. For anyone interested in the proof, I recommend Gödel’s Proof by Nagel instead. It covers the same material in about a tenth the space. (GEB has other philosophical discourses that are interesting, if only as an example of how people can very reasonably mispredict the future. In Hofstader’s case, he posited that chess would only be played at a human level by an AGI.)

manifestsilence 8y ago
I agree that it's way over-long and rambling, but it was my introduction to the topic. Where it really shines is his interesting and controversial thesis that connects Godel's proof with the Church-Turing thesis and other things to form a theory of consciousness as pattern and make the claim that a sufficiently powerful AI is as sentient and meaningful a consciousness as we are. I read Godel's Proof after though, and I agree that it is a far clearer introduction to Godel's theorems.
et1337 8y ago
Absolutely agree. GEB constantly tries to prove the cleverness of the author, complete with winks and nudges. It stacks so many unintuitive analogies on top of each other that I spent most of the time trying to recall which real-world concepts they all mapped to. Also, the book is about 98% Gödel and 2% Escher and Bach. Any time it steps outside its wheelhouse of math and into the realm of philosophy or art, you get the distinct sense that it has no idea what it's talking about. Do yourself a favor and just take discrete math 1 and read a few Wikipedia articles instead.
- mhneu 8y ago
  Do yourself a favor and just take discrete math 1 and read a few Wikipedia articles instead. +100, exactly. I have some familiarity with mathematical logic, and with Bach (though admittedly I'm less familiar with Escher) and I found GEB to be unintuitive at best, and misleading at worst. To be honest, there may not be anything really magic about Goedel's incompleteness theorem once you grasp the core concept, which is: If you encode all proofs into a formal language, you can make a statement that is true but unprovable. (Which is, effectively: "This statement has no proof"). Most of Goedel's work on the incompleteness theorem was on the systematization of proofs, which can be tedious to work through. I found at the time Godel's completeness theorem to be more interesting. Though I never got into model theory or more advanced mathematical logic so, grain of salt.
westoncb 8y ago
I found 'Gödel’s Proof' fascinating—surprisingly more so than GEB, which I'd anticipated loving for years before dipping into it (I didn't finish, but the primary reason was loss of interest). It was one of the first things I came across that gave me the sense of something like 'mathematical system architecture'.
misiti3780 8y ago
If you still have the energy or interest, try I Am A Strange Loop, he wrote in a number of years after and it seemed more approachable
- fredgrott 8y ago
  thank you...I just bought it via amazon
pflats 8y ago
The New Turing Omnibus has a good chapter on the Incompleteness Theorem; it covers the basics in 5 or 6 pages, if memory serves.
carlehewitt 8y ago
Chaitin [2007] presented the following analysis: Godel's proof of inferential undecidability [incompleteness] was too superficial. It didn't get at the real heart of what was going on. It was more tantalizing than anything else. It was not a good reason for something so devastating and fundamental. It was too clever by half. It was too superficial. [It was based on the clever construction] I'm unprovable. So what? This doesn't give any insight how serious the problem is.

raverbashing 8y ago

Yes And GEB's explanation of it is more complete/exact than the one in the article. It is also amazingly mind-twisting. Not the explanation per se, but the theorem. And I think its consequences are under appreciated: no (sufficiently complex) logical system is free from self-contradictions.

wk_end 8y ago
I believe that's a misinterpretation of Goedel; it's an incompleteness theorem, not an unsoundness theorem. Incompleteness: there exist true statements that lack proofs Unsoundness: there exist false statements with proofs If I understand all this correctly, what Goedel demonstrated was that a sufficiently complex logical system could self-reference, and from self-reference unprovable (not contradictory) true statements fall out. By reductio ad absurdum any self-contradictory logical system is useless as a logic because everything is provable in it, so one wonders if such systems should even be considered "logical systems".
- raverbashing 8y ago
  The inconsistency part is the 2nd incompleteness theory. You don't RAA it because you can't prove the system is consistent (because you can't prove the counterexample)
  - wk_end 8y ago
    "Gödel's second incompleteness theorem states no consistent axiomatic system which includes Peano arithmetic can prove its own consistency. Stated more colloquially, any formal system that is interesting enough to formulate its own consistency can prove its own consistency iff it is inconsistent." [1] I believe your position is that "sufficiently complex" == "able to formulate and prove its own consistency"; my position is that such a system would be worthless as a logic, because in such a system you can prove anything. Your second paragraph is inscrutable to me. Are you trying to claim that you can't prove everything with a known inconsistent logic? Are you referring to paraconsistent logics? [1] http://mathworld.wolfram.com/GoedelsSecondIncompletenessTheorem.html http://mathworld.wolfram.com/GoedelsSecondIncompletenessTheo...

DyslexicAtheist 8y ago

obligatory "I am a Strange Loop" reference here for anyone who wants a more polished introduction into the topic from many years later. He wrote GEB when still very young and had time to refine his points in this later book.

chj 8y ago
Unfortunately his style sticks.

draw_down 8y ago

I disagree, I find it to be much more along the lines of “hey this thing is sort of like this other thing, isn’t that cool?” and rather impressed with itself. And it’s extremely tedious when it gets to the place of trying to re-derive formal logic. I don’t really understand why people consider it such a classic, I don’t feel I got much from it at all.