8 ms·
Gödel and the limits of logic
- SoftwareMaven 15y agoGEB sits on my nightstand with too little time to be read. It might have to get bumped up the priority queue a bit.
- generationYpoet 15y agoLikewise. I pulled it off the bookshelf last week and set it on my coffee table, but still haven't had a chance to dive in. This weekend hopefully.
- oz 15y agoSame here. Got through most of the foreword, but haven't found time to continue.
- andybak 15y agoI 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'...
- deleted 15y ago[deleted]
- haliax 15y agoOn a related note, does anyone know where I would look to understand reducibility of formal systems to one another? I'm really interested by questions like: Why is second order logic irreducible to first order logic if I could use first order logic to reason about the behavior of a turing machine running a second order logic theorem prover with whatever inputs I like? How do I get something that can do what I can do, which is to say take any formal system and prove theorems with it? How do you determine what formal systems are "valid" logics? (Leading to sensible conclusions rather than nonsense like A & ~A)
- Rickasaurus 15y agoGodel Escher Bach is a great book (it's entertaining and informative) for learning about formal systems. There are general rules (rules of inference) for their construction from axioms that will keep you from going wrong.
- haliax 15y agoI've read it, but clearly didn't digest enough (a common problem I'm told :P). I will take another look, thanks!
- JamesLeonis 15y agoIf 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 http://reddit.com/r/GEB
- Rickasaurus 15y agoOh 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.
- haliax 15y agoAwesome, thanks!
- nodemaker 15y agoMy intelligence fails me whenever I try!
- ionfish 15y ago'Reducibility' in general is an informal notion, and as such there are many different technically precise ways of capturing aspects of it. Mutual interpretability and bi-interpretability are two of these, but they apply to formal systems with the same underlying logic (that is, the same semantics and proof theory). There are also many other notions of translation between different logics like Gödel–Gentzen negative translation between classical logic and intuitionistic logic. I'm not sure if there is a good introduction to all of these different ways of capturing reducibility, but you could try asking on math.stackexchange.com, there are usually helpful responses to reference requests there. Second order logic does not have a complete proof theory, so your Turing machine will not be able to compute the consequences of a theory formulated in second order logic. This can be avoided by employing Henkin semantics, but then you're not working with full second order logic anymore. Stewart Shapiro's 2000 book, Foundations without Foundationalism: A Case for Second-Order Logic has the technical details should you be interested.
- jpdoctor 15y agoIn 1949 he demonstrated that universes in which time travel into the past is possible were compatible with Einstein's equations. Wait, what?! Anyone have a ref? Edit: Thanks to andyjohnson and vbtemp. TIA for others too.
- vbtemp 15y agoLook at http://en.wikipedia.org/wiki/Closed_timelike_curve http://en.wikipedia.org/wiki/Closed_timelike_curve I.e., "Closed timelike curves". I'm not expert in this matter, but it's a conceptual possibility that fits into general relativity.
- andyjohnson0 15y agoHe discovered a solution to Einstein's field equations that permits closed timelike curves if the universe is rotating. http://en.wikipedia.org/wiki/Godel_metric http://en.wikipedia.org/wiki/Godel_metric "This solution has many strange properties, discussed below, in particular the existence of closed timelike curves which would allow for a form of time travel in the type of universe described by the solution. Its definition is somewhat artificial (the value of the cosmological constant must be carefully chosen to match the density of the dust grains), but this spacetime is regarded as an important pedagogical example"
- deleted 15y ago[deleted]
- rmATinnovafy 15y agoIts always fascinating to read about Gödel. I have not read GEB, yet reading about his findings has really changed the way I think about things. Thanks for posting this article.
- ibrow 15y agoYou may find the Reddit discussion about GEB of interest. http://www.reddit.com/r/geb http://www.reddit.com/r/geb
- rmATinnovafy 15y agoThank you!
- vbtemp 15y agoWhen 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 15y 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 15y 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 15y 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?
- ColinWright 15y agoRelated: Logicomix http://news.ycombinator.com/item?id=3991687 http://news.ycombinator.com/item?id=3991687 http://www.logicomix.com/en/ http://www.logicomix.com/en/ Mentioned in glowing terms here on HN many times: http://www.hnsearch.com/search#request/all&q=logicomix http://www.hnsearch.com/search#request/all&q=logicomix http://news.ycombinator.com/item?id=846451 http://news.ycombinator.com/item?id=846451 http://news.ycombinator.com/item?id=870762 http://news.ycombinator.com/item?id=870762 http://news.ycombinator.com/item?id=874471 http://news.ycombinator.com/item?id=874471 http://news.ycombinator.com/item?id=3690254 http://news.ycombinator.com/item?id=3690254 It was my present for proofing an early draft of "Here's Looking at Euclid" / "Alex's Adventures in Numberland"
- jaysonelliot 15y agoAs an aside, if you look at the photo credit on that great color photo of Einstein and Gödel, it was snapped by Oskar Morgenstern, one of the fathers of game theory. http://en.wikipedia.org/wiki/Oskar_Morgenstern http://en.wikipedia.org/wiki/Oskar_Morgenstern Morgenstern and Einstein were Gödel's closest friends, I've just now learned. It gives me goosebumps looking at that photo and imagining the three of them on that lawn. Semi-related, here's an account of Gödel's "pent-up lecture" about the inconsistencies in the American constitution that he told to his citizenship examiner: http://morgenstern.jeffreykegler.com/ http://morgenstern.jeffreykegler.com/
- why-el 15y agoThanks for the links. I read the account. I was surprised to see that Morgenstern didn't mention Gödel's arguments. It only made a reference to the steps leading up to Gödel's own findings, like what he read on and how much time it took him, but never mentioned the substantial argument, which is what I wanted to read.
- ChrisHugh 15y agoWhat I get out of Goedel is this: There are some things that are true that cannot be proved.
- vbtemp 15y agoBe careful. That's a naive view, and drawing more conclusion than I think you mean. This it more like it: For any consistent, finite axiomatized formal system that is sufficiently expressive (such as the Principia Mathematica), you can construct a sentence in the language of that formal system that asserts its own un-provability. Therefore, there does not exist a mechanistic method for enumerating over all true statements in the language of that formal system. By stating "there are some true things that cannot be proved" goes too philosophy deep, and is outside of our pay-grade. Just consider: humans don't reason based on mechanistic principles - and there's no proof as to the expressability of natural language (though we can be sure it's aggravatingly inconsistent) EDIT: I just want to say that in general, if someone does not really grasp the technical notion of a formal system, consistency, expressiveness, provability, soundness, or recursive enumeration, then it is basically impossible for them to appreciate the incompleteness theorems, and they are very likely to grossly misrepresent it.
- haliax 15y ago> humans don't reason based on mechanistic principles Do you support an empiricist view of logic then (http://en.wikipedia.org/wiki/Is_logic_empirical%3F http://en.wikipedia.org/wiki/Is_logic_empirical%3F) ? That we justify logical rules because they so strongly correspond with our own experiences?
- vbtemp 15y agoNot really. I'm just saying we don't go around all day doing logic-algebra in our head and saying only true, consistent things :)
- haliax 15y agoAhh, fair enough. I'd have to agree with you there. My guess is that that plus being able to inductively generate axioms from experience are largely what let us escape that particular weakness of formal systems.
- ionfish 15y ago"It's like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you'll always end up with some that won't fit in the end." I really don't understand this analogy. The first incompleteness theorem shows that there are statements true of the natural numbers which aren't provable from any sufficiently strong recursive theory. It's more like Th(N) (the set of statements true of the natural numbers) being a jigsaw puzzle from which many pieces will always be missing if you start with a recursive set of pieces and try to lay down only those pieces which a provable from your initial set. Nothing "won't fit": there aren't inconsistencies or incompatibilities at work here, but incompleteness.
- te_platt 15y agoPieces of puzzle = true statements about the natural numbers. Pieces already put together = proved true statements. Pieces that won't fit = true but unprovable statements. Of course every analogy breaks down somewhere but I thought this one was pretty good.
- ionfish 15y agoThe point must surely be that one can add the these true-but-unprovable statements to the original axioms without contradiction. They fit just fine: they're all elements of Th(N). It's a poor analogy because the natural way of thinking of a jigsaw puzzle is of a set of elements (pieces) that are consistent (every piece has a place), so if a piece doesn't fit then it's not consistent with the others. But this is false if the pieces are statements in the language of arithmetic that are true of the natural numbers.
- stiff 15y agoI think the point is that if you try to add those unprovable theorems to the system to try to make it complete it becomes inconsistent. See for example: http://en.wikipedia.org/wiki/Consistency_proof#Consistency_and_completeness_in_arithmetic http://en.wikipedia.org/wiki/Consistency_proof#Consistency_a... Moreover, Gödel's second incompleteness theorem shows that the consistency of sufficiently strong effective theories of arithmetic can be tested in a particular way. Such a theory is consistent if and only if it does not prove a particular sentence, called the Gödel sentence of the theory, which is a formalized statement of the claim that the theory is indeed consistent.
- Fice 15y agoStephen Hawking «Gödel and the end of physics» http://www.damtp.cam.ac.uk/events/strings02/dirac/hawking/ http://www.damtp.cam.ac.uk/events/strings02/dirac/hawking/
- lcargill99 15y agoWhile that's biographically interesting, you really don't get off the hook from understanding that he used basically the same approach of Cantor's diagonalization.
- tluyben2 15y agoFor people interested in the original from 1931: http://www.w-k-essler.de/pdfs/goedel.pdf http://www.w-k-essler.de/pdfs/goedel.pdf (in German). Work of art IMHO.
- ttttannebaum 15y ago"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.