Show HN: I recently gave a talk on the incompleteness theorem, specifically expressed in the language of software. It starts with a bit of historical background and a discussion of some of the philosophical context in which he carried out his work. The second half of the talk is my attempt to show the beautiful essential idea at the core of Godel's idea, pitched to a technically knowledgeable general audience. These are the slides from the talk, not translated into web pages; YMMV.
Link: https://www.gregfjohnson.com/godel_incompleteness/
How Gödel's Proof Works (2020)
31–40 of 74 posts
Re: How Gödel's Proof Works (2020)
#32I am wondering if I'm just not smart enough to understand, but I've managed to slog through GEB and in the end the proof seems contrived, it stands on self reference.
Nagel & Newman is much better if you find GEB a slog (which was also my experience). However, Gödel’s theorem is fundamentally due to self reference. But so is the fact that the power set of countable infinity is uncountable, in a similar way.
Re: How Gödel's Proof Works (2020)
#33Gödels incompleteness is just an example of the fact that you cant determine the outcome of infinite regression (in the general case).
The same as me asking you to give me the last digit of pi.
I am a bit annoyed by pop science always twisting it to sound so convoluted.
Re: How Gödel's Proof Works (2020)
#34> However, although G is undecidable, it’s clearly true. That's... not really true; it's surprising to see it in Quanta, of all places. Godel's (separate) completeness theorem says that in first-order logic, anything that's semantically true in all possible scenarios can be syntactically proved. So, if G is "clearly true", that ought to make it provable. The theorems don't contradict each other because in FOL, G is n…
[deleted]
Re: How Gödel's Proof Works (2020)
#35Gödels incompleteness is just an example of the fact that you cant determine the outcome of infinite regression (in the general case). The same as me asking you to give me the last digit of pi. I am a bit annoyed by pop science always twisting it to sound so convoluted.
I thought it was sorting an infinite set of infinite strings as the first step in the "algorithm" that seemed sketchy. [0]
It's definitely not a constructive proof, even though it pretends to be; none of the mathematical objects can be constructed, nor can any of the algorithmic steps be executed.
That said, it's far less well-known that the workaround (if you find it to be true) is trivially easy (from Alfred Tarski), making it kind of a useless theorem in practice.
[0] You might think, well, I'll just write out the strings in order by using a generator! No sorting needed... But you have to write the strings down to perform the algorithm, and it takes infinite time to write down the first string, so you'll never even get to the others which is when you do the diagonalization trick. Like I said: it's not constructive, none of it can actually be done.
Re: How Gödel's Proof Works (2020)
#36Kind of annoying that literally every article or link shared about this always goes on with some massive introduction of the past instead of just getting to the point.
2+2=4 without 7 paragraphs about humanity wanting numerical representations of quantities and the various number systems devised throughout history before they actually gloss over the actual facts and details.
Re: How Gödel's Proof Works (2020)
#37"Gödel's Proof" by Ernest Nagel and James R. Newman helped me to get it at some point.
On Amazon: https://www.amazon.com/Godels-Proof-Ernest-Nagel-ebook/dp/B0...>
I might even pick up an ebook version if I can find it somewhere else. Been a while.
Re: How Gödel's Proof Works (2020)
#38Earlier quoted context omitted.
I have not read GEB but I thought his second book, I am a Strange Loop, did a pretty good job of connecting the idea of self referential loops (like in godels proof) to consciousness and art and such.
I am a Strange Loop is basically GEB but written properly instead of being a random collation of ideas. Unrusprisingly, since many years went by. But I still love the quirkiness of GEB (Also, he has other books between the two, I deeply enjoyed Le Ton Beau de Marot, about translations)
Thanks for the suggestions. Just checked out some of Le Ton Beau de Marot, will most likely read the rest.
Actually, I was recently wondering whether poems can be interpreted as "efficient" computer programs. Words in a sentence/essay just connect different objects in space and time (syntactically and semantically) to form some concept, kind of like a program. A poem just uses higher order abstractions (imagery) to express the same concepts in fewer words.
So this book should be great!
Re: How Gödel's Proof Works (2020)
#39"Gödel's Proof" by Ernest Nagel and James R. Newman helped me to get it at some point. On Amazon: https://www.amazon.com/Godels-Proof-Ernest-Nagel-ebook/dp/B0... > I might even pick up an ebook version if I can find it somewhere else. Been a while.
Also recommend this book. Very concise too, it's only around 100 pages.
Re: How Gödel's Proof Works (2020)
#40This article is the most concise presentation of GP ... and of the conclusion it leads to ... I've seen.
"Opposite statements, G and ~G, can’t both be true in a consistent axiomatic system."