3 ms·
Some computer science problems are basically reformulations of incompleteness theorems (which makes proving incompleteness even easier, at least for someone fam
by karlicoss 7y ago
Some computer science problems are basically reformulations of incompleteness theorems (which makes proving incompleteness even easier, at least for someone familiar with programming).
E.g. see "Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?"
https://cs.stackexchange.com/questions/419/is-there-any-concrete-relation-between-g%C3%B6dels-incompleteness-theorem-the-halti https://cs.stackexchange.com/questions/419/is-there-any-conc...
- ProfHewitt 7y ago[Turing 1936] pointed out that the theorem of computational undecidability of the halting problem is rather different than Gödel's theorem of the inferential undecidability of I'mUnprovable. In strongly-typed theories, computational undecidability of the halting problem can be used to prove inferential undecidability but not vice versa because the proposition I'mUnprovable does not exist.