4 ms·
> there are whole classes of problems that are no longer being worked on because they're impossible to solve. Genuinely curious - what problems? (Outside speci
by libraryofbabel 7y ago
> there are whole classes of problems that are no longer being worked on because they're impossible to solve.
Genuinely curious - what problems? (Outside special things in Axomatic Set Theory like the Continuum Hypothesis.) E.g. are there topologists not working on certain problems in Topology because they're know to be undecidable?
- karlicoss 7y agoSome 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.