4 ms·
You're precisely right that it's the self-referentiality that gets us in trouble. Systems which don't have that don't suffer from Gödel-related problems (e.g. p
by Tainnor 3y ago
You're precisely right that it's the self-referentiality that gets us in trouble. Systems which don't have that don't suffer from Gödel-related problems (e.g. propositional logic, or arithmetic without multiplication).
Unfortunately, what Gödel showed is that any logical system that is strong enough to capture addition and multiplication over natural numbers - and nothing more - includes self-referentiality.
That includes the language of arithmetic - you can write down formulas that refer to themselves - and Turing machines (via the recursion theorem, any Turing Machine is equivalent to a machine that knows its own source code). The constructions are a bit technical, but it's possible.
- finnh 3y agoYeah I always thought that the construction of Gödel numbers was always the weakest part of the proof / the biggest leap of faith / the part your prof would just hand-wave as being a valid move. Of course once you get into Turing machines it all flows more naturally, what with all of us being accustomed to "code is just data".
- Tainnor 3y agoI agree that Turing Machines feel more natural to programmers than first-order logic (although "natural" doesn't necessarily mean "rigorously proven"), but there are no leaps of faith involved in Gödel's construction. You can write down "P is provable" as a first-order sentence of arithmetic (which involves some number theoretic tricks), and you can also do the diagonalisation trick that gives you self-referentiality. That's really all you need.