Comment by akoboldfrying
6 months ago
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.