Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by qubex on Sunday May 28, 2023 @04:09PM
(#36107287)
I think you’re confusing computational irreducibility and the halting problem.
[ Parent
| on HN ]
Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by s-zeng on Sunday May 28, 2023 @07:13PM
(#36108723)
I think he might be referring to Rice's Theorem, which to be fair is reducible to the halting problem
Re:The Halting Problem Is Decidable on a Set of Asymptotic P...
by simiones on Monday May 29, 2023 @05:46AM
(#36112341)
Computational irreducibility is one consequence of the halting problem being undecidable. If the halting problem were decidable, there couldn't be any computationally irreducible algorithms.