3 ms·
The undecidability of the halting problem is directly related to the existence of undecidable statements, and several important problems are uncomputable. (The
by whatshisface 7y ago
The undecidability of the halting problem is directly related to the existence of undecidable statements, and several important problems are uncomputable. (The word problem for groups, for example.)
- ProfHewitt 7y agoActually, because of the nonexistence of Gödel’s proposition I'mUnprovable in strongly-typed theories, the computational undecidability of the halting problem can be used to prove inferential undecidability (incompleteness).