5 ms·

I 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 Gode

by rgower 14y ago

I 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 ago
I 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 ago
  extraneous 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 ago
    It's an excellent book, but it's very broad, and requires a commitment in time.
VMG 14y ago
If 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 ago
If 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.
- IsTom 14y ago
  Actually Godel's proof is important to CS, it's an analogue of Turing's Proof concerning undecidable problems.
  - lcargill99 14y ago
    My understanding is that Godel's proof was the inspiration for much of Turing's work.
- nooooooo 14y ago
  The unsolvability of the halting problem has a slightly weaker version of Goedel's first incompleteness theorem as a trivial corollary. You can use Turing machines to prove a stronger statement very easily as well. Therefore the CS perspective is very enlightening. See http://www.scottaaronson.com/blog/?p=710 http://www.scottaaronson.com/blog/?p=710.
vbtemp 14y ago
At the very least a good course in discrete mathematics is a good start (it's also a good start for anything technical as well - one of the most valuable math classes anyone can ever take, as far as I'm concerned) Following that, a good class in the theory of computing: understanding what exactly a generative grammar is, properties of classes of languages (e.g., understanding what "regular languages are closed under complimentation" means), pumping lemma, diagnalization proofs, halting problem. The incompleteness theorem is intimately tied to this. This is the "CS-route" to getting a good understanding in Incompleteness, I'm sure math or physics majors come to approach it in each their own way. Being a little blunt, a background in philosophy (whether it's academic or not) without a solid discrete math background, doesn't help you out at all. This isn't philosophy, it's just a fact about properties of formal systems of sufficient complexity. If you're looking for philosophy you won't find anything too deep in the proof of Incompleteness. The philosophical implications are not clear. However, I do recommend Rebecca Goldstein's book. It's not technical, and she's a Princeton philosopher who will indulge you with possible philosophical ramifications of the theorem (along with a good narrative). I also recommend her other books as well, especially her first novella "The Mind-Body Problem". From a philosophical perspective, the dispute between Goedel and Wittgenstein who never accepted the Incompleteness Theorem "whereof we cannot speak we must pass over in silence", which, ironically, speaks of something of which we cannot speak.
- praptak 14y ago
  > At the very least a good course in discrete mathematics is a good start I believe that the best starting point to get to incompleteness is formal logic. This is the basic set of concepts that lets us make terms, statements and finally proofs the subject of formal mathematical study, thus tying the loop (formally mathematically defined reasoning about formally mathematically defined reasoning :-) ) that leads to Goedels proof. Discrete mathematics is helpful but it is rather low level, the core concepts in incompleteness come from formal logic.
  - vbtemp 14y ago
    I consider a solid discrete math curriculum to provide a reasonable background in first and second order logic
pmb 14y ago
The statement "this fact is not provably true under the axioms of mathematics" is not provably true under the axioms of mathematics. Therefore, it is true, but we can never prove it. I recommend approaching this via uncomputability, and the fact that for every program there is a proof and vice versa.
zerostar07 14y ago
I think it's best to go directly at the source. Wikipedia has a very understandable sketch of proof (which in itself is quite unconventional) that helps understand the motivation and the content of the theorem: http://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s_first_incompleteness_theorem http://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s...
mcguire 14y ago
Whatever approach you take, be sure it includes Torkel Franzén's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse. Although it's pretty good, it may not be where you want to start. But there are a lot of bogus conclusions made by people with a superficial understanding of Gödel and that is the best thing I know pointing out the flaws.
ionfish 14y ago
Do you have a decent understanding of first order logic? If not, sort that out first. Peter Smith has a good list of books to choose from: http://www.logicmatters.net/2012/05/teach-yourself-logic-1-first-order-logic/ http://www.logicmatters.net/2012/05/teach-yourself-logic-1-f... Then get Smith's book An Introduction to Gödel's Theorems. It explains Gödel's results in great detail and doesn't assume too much background knowledge. A certain amount of perseverance will, of course, be required… There's some supplementary material on his website: http://www.logicmatters.net/igt/ http://www.logicmatters.net/igt/
philh 14y ago
Shameless self-promotion: I gave a talk outlining the proof. http://youtu.be/j0NcE3Tnklw http://youtu.be/j0NcE3Tnklw It was aimed at math students, but I don't think I assumed prior knowledge of anything esoteric. Parts of it might be hard to follow without math or CS, I'm not sure.
lcargill99 14y ago
I would recommend coming to terms with "A Transition To Advanced Mathematics". Once you feel like you can plumb Cantor's Diagonalization without nausea :), then read on Godel. GEB is excellent but frothy ( not pointed and a slog ) but is worth it for other reasons. I think that Godel was more important from a social perspective - there is a strong correlation between Postivism and much of the evils in the 20th Century.

by rgower 14y ago

GregBuchholz 14y ago

I 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 ago
extraneous 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 ago
  It's an excellent book, but it's very broad, and requires a commitment in time.

VMG 14y ago

If 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 ago

If 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.

IsTom 14y ago
Actually Godel's proof is important to CS, it's an analogue of Turing's Proof concerning undecidable problems.
- lcargill99 14y ago
  My understanding is that Godel's proof was the inspiration for much of Turing's work.
nooooooo 14y ago
The unsolvability of the halting problem has a slightly weaker version of Goedel's first incompleteness theorem as a trivial corollary. You can use Turing machines to prove a stronger statement very easily as well. Therefore the CS perspective is very enlightening. See http://www.scottaaronson.com/blog/?p=710 http://www.scottaaronson.com/blog/?p=710.

vbtemp 14y ago

At the very least a good course in discrete mathematics is a good start (it's also a good start for anything technical as well - one of the most valuable math classes anyone can ever take, as far as I'm concerned) Following that, a good class in the theory of computing: understanding what exactly a generative grammar is, properties of classes of languages (e.g., understanding what "regular languages are closed under complimentation" means), pumping lemma, diagnalization proofs, halting problem. The incompleteness theorem is intimately tied to this. This is the "CS-route" to getting a good understanding in Incompleteness, I'm sure math or physics majors come to approach it in each their own way. Being a little blunt, a background in philosophy (whether it's academic or not) without a solid discrete math background, doesn't help you out at all. This isn't philosophy, it's just a fact about properties of formal systems of sufficient complexity. If you're looking for philosophy you won't find anything too deep in the proof of Incompleteness. The philosophical implications are not clear. However, I do recommend Rebecca Goldstein's book. It's not technical, and she's a Princeton philosopher who will indulge you with possible philosophical ramifications of the theorem (along with a good narrative). I also recommend her other books as well, especially her first novella "The Mind-Body Problem". From a philosophical perspective, the dispute between Goedel and Wittgenstein who never accepted the Incompleteness Theorem "whereof we cannot speak we must pass over in silence", which, ironically, speaks of something of which we cannot speak.

praptak 14y ago
> At the very least a good course in discrete mathematics is a good start I believe that the best starting point to get to incompleteness is formal logic. This is the basic set of concepts that lets us make terms, statements and finally proofs the subject of formal mathematical study, thus tying the loop (formally mathematically defined reasoning about formally mathematically defined reasoning :-) ) that leads to Goedels proof. Discrete mathematics is helpful but it is rather low level, the core concepts in incompleteness come from formal logic.
- vbtemp 14y ago
  I consider a solid discrete math curriculum to provide a reasonable background in first and second order logic

pmb 14y ago

The statement "this fact is not provably true under the axioms of mathematics" is not provably true under the axioms of mathematics. Therefore, it is true, but we can never prove it. I recommend approaching this via uncomputability, and the fact that for every program there is a proof and vice versa.

zerostar07 14y ago

I think it's best to go directly at the source. Wikipedia has a very understandable sketch of proof (which in itself is quite unconventional) that helps understand the motivation and the content of the theorem: http://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s_first_incompleteness_theorem http://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s...

mcguire 14y ago

Whatever approach you take, be sure it includes Torkel Franzén's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse. Although it's pretty good, it may not be where you want to start. But there are a lot of bogus conclusions made by people with a superficial understanding of Gödel and that is the best thing I know pointing out the flaws.

ionfish 14y ago

Do you have a decent understanding of first order logic? If not, sort that out first. Peter Smith has a good list of books to choose from: http://www.logicmatters.net/2012/05/teach-yourself-logic-1-first-order-logic/ http://www.logicmatters.net/2012/05/teach-yourself-logic-1-f... Then get Smith's book An Introduction to Gödel's Theorems. It explains Gödel's results in great detail and doesn't assume too much background knowledge. A certain amount of perseverance will, of course, be required… There's some supplementary material on his website: http://www.logicmatters.net/igt/ http://www.logicmatters.net/igt/

philh 14y ago

Shameless self-promotion: I gave a talk outlining the proof. http://youtu.be/j0NcE3Tnklw http://youtu.be/j0NcE3Tnklw It was aimed at math students, but I don't think I assumed prior knowledge of anything esoteric. Parts of it might be hard to follow without math or CS, I'm not sure.

lcargill99 14y ago

I would recommend coming to terms with "A Transition To Advanced Mathematics". Once you feel like you can plumb Cantor's Diagonalization without nausea :), then read on Godel. GEB is excellent but frothy ( not pointed and a slog ) but is worth it for other reasons. I think that Godel was more important from a social perspective - there is a strong correlation between Postivism and much of the evils in the 20th Century.