4 ms·
You can also obtain incompleteness from the unsolvability of the halting problem, by noting that if every statement in (say) Peano arithmetic were provable, one
by pfdietz 2mo ago
You can also obtain incompleteness from the unsolvability of the halting problem, by noting that if every statement in (say) Peano arithmetic were provable, one could solve the halting problem. Encode a halting execution of a TM as an integer using Gödel numbers and write a statement that the execution halts. Either that statement or its negation would be provable, so search for proofs for each at the same time.
An additional related theorem is Rogers' recursion theorem, which is how we get programs that, when run, print their own source code (by the theorem this can be done in any Turing complete programming language.)
- GoblinSlayer 2mo agoThat won't work. Gödel number encodes a paradox, but a halting execution of a TM is not a paradox, so can't be written as a Gödel number.
- pfdietz 2mo agoYour word salad is not even wrong. For example: > Gödel number encodes a paradox WTF do you mean by this?
- GoblinSlayer 2mo agoA statement that can't be proved true or false and thus demonstrates incompleteness of logic.
- pfdietz 2mo agoHow is that a paradox? And how does that imply the correct argument I gave doesn't work? (It doesn't imply that.)
- GoblinSlayer 2mo agoParadox is a statement that can't be proved true or false; "this statement is false" is an example of Gödel statement. The argument doesn't work, because execution of a Turing machine can't be expressed as a Gödel number.
- pfdietz 2mo ago> Paradox is a statement that can't be proved true or false No it isn't. > execution of a Turing machine can't be expressed as a Gödel number Yes it can.