Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Gödel and the limits of logic

plus.maths.org

Post reply on HN
Print view View original

61–70 of 80 posts

Re: Gödel and the limits of logic

#61

Post by ionfish »

vbtemp wrote: post #28
rgower wrote: post #27

Earlier quoted context omitted.

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?

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…

Knowing computer science stuff like regular languages is really not required to understand the incompleteness theorems; grasping first order logic, a little arithmetic and some elementary recursion theory is sufficient.

I repeat my objection to the Goldstein book raised elsewhere in this discussion.

Re: Gödel and the limits of logic

#62

Post by philh »

rgower wrote: post #27
vbtemp wrote: post #10

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…

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?

Shameless self-promotion: I gave a talk outlining the proof. 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.

Re: Gödel and the limits of logic

#63

Post by vbtemp »

praptak wrote: post #55
vbtemp wrote: post #28

Earlier quoted context omitted.

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…

> 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 Goe…

I consider a solid discrete math curriculum to provide a reasonable background in first and second order logic

Re: Gödel and the limits of logic

#64

Post by vbtemp »

ionfish wrote: post #48
vbtemp wrote: post #10

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…

The Goldstein book is rubbish. Soloman Feferman destroys it in his LRB review. http://www.lrb.co.uk/v28/n03/solomon-feferman/provenly-unpro... 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 Golds…

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

Re: Gödel and the limits of logic

#65

Post by ionfish »

vbtemp wrote: post #64
ionfish wrote: post #48

Earlier quoted context omitted.

The Goldstein book is rubbish. Soloman Feferman destroys it in his LRB review. http://www.lrb.co.uk/v28/n03/solomon-feferman/provenly-unpro... 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 Golds…

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

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

Re: Gödel and the limits of logic

#66

Post by Rickasaurus »

JamesLeonis wrote: post #38
haliax wrote: post #36

Earlier quoted context omitted.

I've read it, but clearly didn't digest enough (a common problem I'm told :P). I will take another look, thanks!

If you didn't already know about it, there's a Reddit group that's doing a weekly readthrough and discussion. They're on chapter 13 currently. http://reddit.com/r/GEB

Oh man, wish I had seen this sooner. It's been a quite a few years and I'd love to give it another read with a group.

Re: Gödel and the limits of logic

#67

Post by Natsu »

ionfish wrote: post #19
ChrisHugh wrote: post #15

What I get out of Goedel is this: There are some things that are true that cannot be proved.

Provability is relative to a formal system. Whether there are _absolutely undecidable_ statements is more controversial, and still an open question in the philosophy of mathematics. Gödel's disjunction is part of this literature: "Either … the human mind … infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems." Soloman Feferman has written about this, fo…

If anything is absolutely undecidable, I suspect it will be P=NP.

Re: Gödel and the limits of logic

#68

Post by neilc »

vbtemp wrote: post #63
praptak wrote: post #55

Earlier quoted context omitted.

> 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 Goe…

I consider a solid discrete math curriculum to provide a reasonable background in first and second order logic

I would be surprised to find second order logic discussed in an introductory discrete math curriculum.

Re: Gödel and the limits of logic

#69

Post by davvid »

GregBuchholz wrote: post #41
rgower wrote: post #27

Earlier quoted context omitted.

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?

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 hav…

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.

Re: Gödel and the limits of logic

#70

Post by anonymousDan »

zzzmarcus wrote: post #30
vbtemp wrote: post #10

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…

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

+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.
Post reply on HN