6 ms·
When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while
by vbtemp 14y ago
When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well).
These are a few books I recommend:
"Incompleteness - The proof and paradox of Kurt Gödel" by Rebecca Goldstein
"Gödel's Proof" by Ernst Nagel (it's a tiny book, not too technical, but technical enough for anyone with a solid CS background to appreciate and understand)
- malingo 14y agoI've always liked GW Flake's writing on the topic. http://mitpress.mit.edu/books/FLAOH/cbnhtml/excerpts1.html http://mitpress.mit.edu/books/FLAOH/cbnhtml/excerpts1.html
- pndmnm 14y agoNagel's book is a wonderful exposition (three-page-long footnotes aside). In addition to these two, I might recommend Torkel Franzén's book "Gödel's Theorem: An Incomplete Guide to Its Use and Abuse". Some of the content is fairly technical but not inaccessible by any means. If you're interested in the corner cases of how incompleteness theorems can be applied, it's a terrific resource.
- rgower 14y agoI have no background in CS or Math, but a lot of philosophy. In other words, I'm a highly interested layman. What's my best plan of action to understanding Godel's theory? Maybe the best approach would be an entry level book on CS?
- GregBuchholz 14y agoI always liked "Godels Theorem Simplified". It doesn't rely on heavy technical prerequisites in mathematics or CS. It is pretty much as advertised, a simplification of Godel's original proof. Godel used a more complicated encoding scheme using prime numbers, which Gensler replaces with a simpler encoding scheme. He walks you through various less powerful formal systems, before you get to one complicated enough to have incompleteness issues. There is also discussion about the philosophical ramifications of Godel's theroems. http://www.amazon.com/Godels-Theorem-Simplified-Harry-Gensler/dp/081913869X/ http://www.amazon.com/Godels-Theorem-Simplified-Harry-Gensle... "Godel, Escher, Bach" is another interesting read, but that volume does have a lot of extraneous fluff.
- davvid 14y agoextraneous fluff Hey, now. Gödel, Escher, Bach has character and is IMO a very fun book. You might have to read it more then once, though.. it's self-referential and strange-loopy in that way.
- lcargill99 14y agoIt's an excellent book, but it's very broad, and requires a commitment in time.
- VMG 14y agoIf you want to start off easy listen to this: http://www.radiolab.org/2011/oct/04/ http://www.radiolab.org/2011/oct/04/
- lmkg 14y agoIf you want to understand just Godel's theorem, you probably want to focus on Logic more than Math or CS. Godel's proof involves qualifying over first-order logic statements and logical properties of numbers much more than it involves computation or numerics. The most nitty-gritty part is Godel encodings, but it's not that computationally intensive, and the details actually aren't that relevant. If you want to understand the ramifications of Godel's theory, it impacts math more directly than CS. The most directly impacted branches of math are the more "fundamental" ones like Set Theory. Limitations of CS has a lot more to do with Turing's theorems than Godel's.
- zzzmarcus 14y agoAnother book that has several chapters related to GEB is David Deutsch's "The Beginning of Infinity." It's a very accessible read, and for me, eye-opening in more than one way.
- anonymousDan 14y ago+1, a really enjoyable but provocative read. With respect to Godel, Roger Penrose's "Shadows of the Mind" gives a pretty good insight into the implications of Godels theorems.
- ionfish 14y agoThe Goldstein book is rubbish. Soloman Feferman destroys it in his LRB review. http://www.lrb.co.uk/v28/n03/solomon-feferman/provenly-unprovable http://www.lrb.co.uk/v28/n03/solomon-feferman/provenly-unpro... http://math.stanford.edu/~feferman/papers/lrb.pdf http://math.stanford.edu/~feferman/papers/lrb.pdf (full text) "Those who are fascinated by Gödel's theorems—and the general idea of limits to what we can know—may still hunger for a more universal view of their possible significance. But they should not be satisfied with Goldstein's 'vast and messy' goulash, hers is not a recipe for true understanding."
- altrego99 14y agoI read this stuff in "The Emperor's New Mind" by Roger Penrose. It not only talks about this, but introduces to Relativity, Quantum Mechanics, Phase Spaces. It also builds up all the mathematics required, so if you know what complex numbers are - that will be more than enough to follow and understand the concepts introduced well enough. Very highly recommended. The second part somehow was not as interesting though.
- lcargill99 14y ago"Emperor" is a problematic work at best. He's skyhooking.
- vbtemp 14y agoI wouldn't say it's rubbish - but it's no great authority on communicating the proof itself, certainly. It is a good biography though, covering the roots in the Vienna circle and the disagreements with Wittgenstein. Edit: Thanks for posting that pdf though, I enjoyed reading it.
- ionfish 14y agoIf it's a biography you want, you'd be better off with John Dawson's one (he is, of course, the author of the article linked at the root).
- omaranto 14y agoMy favorite book about incompleteness is Raymond Smullyan's Godel's Incompleteness Theorems.