Hacker News new | ask | show | jobs
by Kranar 303 days ago
The objection, which I agree with, is to the statement "Any method that works for some programs will fail for others, and in some cases, no method will work."

There is no case where no method whatsoever will work. It's true that for any method, there are cases where it fails but it's not true that there exist cases for which every method fails.
2 comments
mistercow 300 days ago
Yeah, apparently I didn’t communicate that well enough. But I think this is a subtle and common point of confusion.

There are machines which are very, very hard to determine whether they halt or not, and so people end up thinking that there must be specific machines for which no Turing machine can decide halting correctly. But that’s just not true. Every “attempted halting decider” has its own infinite set of failure cases, which are specific to that machine, and not fundamental to the input machines.

This feels really strange, and trying to turn that other intuitive sense into something meaningful and reasonably formal is an interesting exercise, but it’s tricky.

link
JohnKemeny 303 days ago
Okay, I see what you mean.

It really hinges on what is meant by "this question", i.e., Given the code of a computer program, can you tell whether it will eventually stop or run forever?

If what's given to you is the code and its input, then I think the statement's correct.

However, if the input is assumed to be either the code itself or any other fixed thing, then I agree with you.

link
jakelazaroff 303 days ago
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.

link