News for hackers. Stuff that matters.
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.
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.
Re:The Halting Problem Is Decidable on a Set of Asymptotic P... by jameshart on Monday May 29, 2023 @09:48AM (#36113918)
Right, these things are all corollaries of one another.