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

71–80 of 80 posts

Re: Gödel and the limits of logic

#71

Post by altrego99 »

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

Re: Gödel and the limits of logic

#72

Post by nooooooo »

lmkg wrote: post #39
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?

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

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.

Re: Gödel and the limits of logic

#74

Post by lcargill99 »

altrego99 wrote: post #71
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 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.

"Emperor" is a problematic work at best. He's skyhooking.

Re: Gödel and the limits of logic

#75

Post by lcargill99 »

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?

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.

Re: Gödel and the limits of logic

#76

Post by lcargill99 »

IsTom wrote: post #52
lmkg wrote: post #39

Earlier quoted context omitted.

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

Actually Godel's proof is important to CS, it's an analogue of Turing's Proof concerning undecidable problems.

My understanding is that Godel's proof was the inspiration for much of Turing's work.

Re: Gödel and the limits of logic

#77

Post by lcargill99 »

davvid wrote: post #69
GregBuchholz wrote: post #41

Earlier quoted context omitted.

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.

It's an excellent book, but it's very broad, and requires a commitment in time.

Re: Gödel and the limits of logic

#78

Post by andybak »

oz wrote: post #20
SoftwareMaven wrote: post #2

GEB sits on my nightstand with too little time to be read. It might have to get bumped up the priority queue a bit.

Same here. Got through most of the foreword, but haven't found time to continue.

I read it a long time ago (late teens/early twenties) but it changed my intellectual world and gave me an insight into things that I might never have been introduced to. Hard to know whether it would have the same impact now or the same impact for others but I rate it very highly for personal reasons. Also - Rudy Rucker's 'Infinity and the Mind'...

Re: Gödel and the limits of logic

#80

Post by ttttannebaum »

"Another result that derives from Gödel's ideas is the demonstration that no program that does not alter a computer's operating system can detect all programs that do. In other words, no program can find all the viruses on your computer, unless it interferes with and alters the operating system."

I think I just heard a 'pop'ping sound.. but really, writers try too hard sometimes to make this stuff accessible to people. I don't think someone who is going to get a whole half-way into the article is going to need such reductionism to catch their interest; I'd honestly be more excited if the actual symbolic definition of the theorem was shown to me at that point.

Post reply on HN