3 ms·

This blog post gets way too caught up in Gödel numbers, which are merely a technical detail (specifically how the encoding is done is irrelevant). A clever deta

by dvt 6mo ago

This blog post gets way too caught up in Gödel numbers, which are merely a technical detail (specifically how the encoding is done is irrelevant). A clever detail, but a detail nonetheless. Author gets lost in the sauce and kind of misses the forest for the trees. In class, we used Löb's Theorem[1] to prove Gödel, which is much more grokkable (and arguably even more clever). If you truly get Löb, it'll kind of blow your mind. [1] https://inference-review.com/article/loebs-theorem-and-currys-paradox https://inference-review.com/article/loebs-theorem-and-curry...

qnleigh 6mo ago
Yeah, I think it would be better to first explain the liar's paradox to give the broad brush strokes, and then go into the details of Gôdel numbering. It seems like most expositions of Gödel's incompleteness theorem go into a surprising amount of detail about Gödel numbering. In a way it's nice though, because you see that the proof is actually pretty elementary and doesn't require fancy math as a prerequisite.
annie511266728 6mo ago
Yeah, I think that's the tradeoff. Löb gets you to the main idea faster, but Gödel numbering is the part that makes it feel like the system is actually doing it itself. Without that step, it can start to feel a bit too close to the liar paradox.
- cousin_it 6mo ago
  Yeah. I'd say half of the work is Gödel numbering and the other half is the diagonal lemma.
  - mjh2539 6mo ago
    This is the most apt answer I've read thus far.
Nevermark 6mo ago
Other names for Gödel encoding: Digital. Binary. Zorros and Unos. Today Gödel encoding is so pervasive, it’s easy to miss that everything is trivially Gödel encladed. Because like most everything invisible, it’s right in front of us. We Gödel our memes and gift cards, and (pick your poison) pr0ns. Colors and AI’s, lax ASMR’s and our (sneaky don’t read me) terms of service. Even this very small humble . Gödel isn’t eating the world. Gödel already pööped it.
- manofmanysmiles 6mo ago
  Do you recommend reading "Gödel, Escher, Bach: an Eternal Golden Braid"?
- jb1991 6mo ago
  You are suggesting Godel created the punctuation mark known as a period? Obviously not. But I'm not sure what you are trying to say..
  - Nevermark 6mo ago
    That period was encoded in a symbol string, i.e. it is a bit string. Today we encode everything in bi-symbol strings. This was not common when Gödel crafted his incompleteness theorem. And at the time it was a novel approach for setting up a context for testing the limits of computing. Some people can still be struck by it as novel when reading the proof, because in context it was, and still feels that way. But today "symbol string" representation is ordinary and pervasive.
- bazoom42 6mo ago
  Gödel did not invent encoding. Morse was widely used before Gödel.
  - Nevermark 6mo ago
    Morse didn't conceptually extend encoding to self-referential symbolic systems. Morse's insight was pure communication of symbols devoid of meaning. Important but nowhere near the same. Today, general symbolic encoding is viewed as trivial. Every symbol we have is pervasively encoded as bits, so of course entire expressions are. So Morse's code might seem comparable. But what Gödel invented went well beyond Morse. We are just jaded with regard to his insight now.
DarkNova6 6mo ago
As a non-mathematician I always wondered about one thing. Because the way I interpret the Incompleteness Theory is that "you cannot have a universal system of infinite expressiveness, because you will need a more expressive one to prove it". In other words, you can't have a top-down universal system. But you very well can have well described ones perfectly describe observable behaviour without defects. Or is this too reductive?
- dvt 6mo ago
  The easiest way to think about it is like this: We have these things called systems: a "system" is anything that follows rules: a board game, traffic, the English language, math, C++, etc. Some systems are smart and they can talk about themselves, but others can't. For example, Tic-Tac-Toe can't talk about Tic-Tac-Toe, but English can talk about English. Gödel is interested in smart systems because dumb systems are boring. Some systems are useful: they are "useful" if they always say true things. So math is more useful than English. I can lie in English, but I can't lie in math. (Formally, this is what we call consistency). So here's a problem for you: suppose we have a smart-useful-system, call it SUS. SUS should be able to say "SUS is useful." It can talk about itself and it can't lie, so we should have no problem, right? Gödel showed that if our system can actually say that about itself, it wasn't useful to begin with. For a few centuries, philosophers and mathematicians were trying to come up with the "one perfect system": useful, smart, and also complete (it can say all true things), and a few more properties. Turns out such a system is impossible. NB: I use the words "say" or "talk about" in a very hand-wavy fashion, sometimes I mean Prove(), sometimes I mean Entail(). The details are very nuanced, and this isn't meant to be a deep dive.
ghywertelling 6mo ago
Godel's 1st Incompleteness Theorem - Proof by Diagonalization https://www.youtube.com/watch?v=PpSxqde0af4 https://www.youtube.com/watch?v=PpSxqde0af4 This is another good exposition.

by dvt 6mo ago

qnleigh 6mo ago

Yeah, I think it would be better to first explain the liar's paradox to give the broad brush strokes, and then go into the details of Gôdel numbering. It seems like most expositions of Gödel's incompleteness theorem go into a surprising amount of detail about Gödel numbering. In a way it's nice though, because you see that the proof is actually pretty elementary and doesn't require fancy math as a prerequisite.

annie511266728 6mo ago

Yeah, I think that's the tradeoff. Löb gets you to the main idea faster, but Gödel numbering is the part that makes it feel like the system is actually doing it itself. Without that step, it can start to feel a bit too close to the liar paradox.

cousin_it 6mo ago
Yeah. I'd say half of the work is Gödel numbering and the other half is the diagonal lemma.
- mjh2539 6mo ago
  This is the most apt answer I've read thus far.

Nevermark 6mo ago

Other names for Gödel encoding: Digital. Binary. Zorros and Unos. Today Gödel encoding is so pervasive, it’s easy to miss that everything is trivially Gödel encladed. Because like most everything invisible, it’s right in front of us. We Gödel our memes and gift cards, and (pick your poison) pr0ns. Colors and AI’s, lax ASMR’s and our (sneaky don’t read me) terms of service. Even this very small humble . Gödel isn’t eating the world. Gödel already pööped it.

manofmanysmiles 6mo ago
Do you recommend reading "Gödel, Escher, Bach: an Eternal Golden Braid"?
jb1991 6mo ago
You are suggesting Godel created the punctuation mark known as a period? Obviously not. But I'm not sure what you are trying to say..
- Nevermark 6mo ago
  That period was encoded in a symbol string, i.e. it is a bit string. Today we encode everything in bi-symbol strings. This was not common when Gödel crafted his incompleteness theorem. And at the time it was a novel approach for setting up a context for testing the limits of computing. Some people can still be struck by it as novel when reading the proof, because in context it was, and still feels that way. But today "symbol string" representation is ordinary and pervasive.
bazoom42 6mo ago
Gödel did not invent encoding. Morse was widely used before Gödel.
- Nevermark 6mo ago
  Morse didn't conceptually extend encoding to self-referential symbolic systems. Morse's insight was pure communication of symbols devoid of meaning. Important but nowhere near the same. Today, general symbolic encoding is viewed as trivial. Every symbol we have is pervasively encoded as bits, so of course entire expressions are. So Morse's code might seem comparable. But what Gödel invented went well beyond Morse. We are just jaded with regard to his insight now.

DarkNova6 6mo ago

As a non-mathematician I always wondered about one thing. Because the way I interpret the Incompleteness Theory is that "you cannot have a universal system of infinite expressiveness, because you will need a more expressive one to prove it". In other words, you can't have a top-down universal system. But you very well can have well described ones perfectly describe observable behaviour without defects. Or is this too reductive?

dvt 6mo ago
The easiest way to think about it is like this: We have these things called systems: a "system" is anything that follows rules: a board game, traffic, the English language, math, C++, etc. Some systems are smart and they can talk about themselves, but others can't. For example, Tic-Tac-Toe can't talk about Tic-Tac-Toe, but English can talk about English. Gödel is interested in smart systems because dumb systems are boring. Some systems are useful: they are "useful" if they always say true things. So math is more useful than English. I can lie in English, but I can't lie in math. (Formally, this is what we call consistency). So here's a problem for you: suppose we have a smart-useful-system, call it SUS. SUS should be able to say "SUS is useful." It can talk about itself and it can't lie, so we should have no problem, right? Gödel showed that if our system can actually say that about itself, it wasn't useful to begin with. For a few centuries, philosophers and mathematicians were trying to come up with the "one perfect system": useful, smart, and also complete (it can say all true things), and a few more properties. Turns out such a system is impossible. NB: I use the words "say" or "talk about" in a very hand-wavy fashion, sometimes I mean Prove(), sometimes I mean Entail(). The details are very nuanced, and this isn't meant to be a deep dive.

ghywertelling 6mo ago

Godel's 1st Incompleteness Theorem - Proof by Diagonalization https://www.youtube.com/watch?v=PpSxqde0af4 https://www.youtube.com/watch?v=PpSxqde0af4 This is another good exposition.