Comment by mistercow
6 months ago
> In 1936, the pioneering logician Alan Turing proved that there’s no universal procedure for answering this question, which became known as the halting problem. Any method that works for some programs will fail for others, and in some cases, no method will work.
This is weirdly stated. The first sentence is correct. But trivially, either a machine that always says “yes” or a machine that always says “no” will give the correct answer for any given case.
Given a particular set of axioms, there are machines which do not halt, but which cannot be proven not to halt, and maybe that’s what the article means. But that’s going beyond the halting problem.
"this question" is Given the code of a computer program, can you tell whether it will eventually stop or run forever?
It is indeed the Halting problem. (Except that they forgot to state what the input is (the code itself).
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.
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.
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.
2 replies →
)
I think your quantifiers are in the wrong order.
Because you wrote "But trivially, either a machine...", I think you must think that the second sentence in your quote means "For every program p, there does not exist any method m that, when applied to p, determines whether p halts" -- which would clearly be false, since it allows every program to have its own method (and as you say, just 2 "constant-valued methods" suffice). But I interpret that second sentence in your quote as "There does not exist a single method m that, when applied to any program p, determines whether p halts", which is correct.
>Given a particular set of axioms, there are machines which do not halt, but which cannot be proven not to halt, and maybe that’s what the article means.
I also think that's what the article means, and I think it's a very nice way of putting it, though it's an interesting enough wrinkle to discuss further.
I think their issue is with the end of the sentence: "and in some cases, no method will work", which I interpret to say there are some programs for which no method can determine whether they will halt.
That's obviously incorrect; the program either halts or it does not. So if you had function that always returned true and another that always returned false, one of those functions would correctly tell you whether a given program will halt — for every program that could possibly exist.
The hard part is figuring out which function to use :)
A watch that just says PM correct some of the time.