Actually Turing used Gödel’s approach to prove halting problem is unsolvable within Turing Machines. So using Halting Problem to prove Gödel’s incompleteness theorem looks like a recursive loop. Halting problem proves Gödel, gödel proves halting problem.... goes on.
-
-
This Tweet is unavailable.
-
This Tweet is unavailable.
- Show replies
-
-
-
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
This is essentialy the essence of the original proof, the technical part is that the Peano exioms can encode this statement on Turing machines.
-
I love that the first proof boils down to a very clever extension of the "this statement is false" trick we teach kids.
- Show replies
New conversation -
-
-
It's also interesting that proofs of both Godel's theorem and the halting problem are based on a similar diagonalization argument, which also suggests that they are closely related.
-
Uncomputability is the deeper reason for incompleteness. For Turing showed something stronger i.e. soundness + completeness implied you could systematically settle anything you query your formal axiomatic system.
- Show replies
New conversation -
-
-
You mean Refutational Reasoning?
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
The puzzling part of Gödel theorem IMO is that there are undecidable propositions of the form "exists k, s.t. P(k)" since the existence of such a k would provide a proof, so k cannot exist, so I do not understand "exists k".
-
The k is not a natural number but an element of a non standard model of arithmetic which does not code for a proof.
- Show replies
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.