Re:Busy Beaver Hunters Reach Numbers That Overwhelm Ordinary...
by jakelazaroff on Monday August 25, 2025 @07:10PM
(#45020297)
I don't see how what's given to you changes things? If there's ambiguity, I think it's in whether the question is actually the halting problem:
If it is the halting problem — less ambiguously written as "given the code of a computer program and its input, will it run forever?" — then the statement is incorrect: there is a method that returns the correct result for every possible program and input.
If it is about proving whether a machine halts — not getting it right by chance, but showing that a particular machine halts or runs forever — then the statement is correct, for any set of axioms there are Turing machines that cannot be proven to halt or run forever using those axioms.
If it is the halting problem — less ambiguously written as "given the code of a computer program and its input, will it run forever?" — then the statement is incorrect: there is a method that returns the correct result for every possible program and input.
If it is about proving whether a machine halts — not getting it right by chance, but showing that a particular machine halts or runs forever — then the statement is correct, for any set of axioms there are Turing machines that cannot be proven to halt or run forever using those axioms.