0
$\begingroup$

Please note I don't use any of the "verifier" notation, I only concern definitions made with DTM and NTM .

Now there are two definitions of decidability:

1. A set (predicate) is decidable (solvable) iff exist a machine (DTM/NTM) M(x) that accepts iff x∈A, and rejects iff x∉A. i.e. if it halts correctly against all input.

Many sources supports this definition, among them the clearest one is on Wikipedia:

A Turing machine is said to recognize a language (recall that "problem" and "language" are largely synonymous in computability and complexity theory) if it accepts all inputs that are in the language and is said to decide a language if it additionally rejects all inputs that are not in the language (certain inputs may cause a Turing machine to run forever, so decidability places the additional constraint over recognizability that the Turing machine must halt on all inputs). A Turing machine that "solves" a problem is generally meant to mean one that decides the language.

2. A set (predicate) is decidable (solvable) iff exist a machine (DTM/NTM) M(x) that accepts iff x∈A i.e. if it halts correctly against all elements with “yes” as output.

This is posed by Another stackexchange problem, under the user Shitikanth, with 10+ votes.

Now I am genuinely confused. Intuitively I think 1 is correct, as halting problem is obviously decidable against all "YES" input -- you just have to run them and by definition they terminate in finite time, which obviously not making halting problem decidable.

$\endgroup$
1
  • 1
    $\begingroup$ The second definition corresponds to the recursively enumerable sets. Also, note that it is not the definition provided in the linked answer. They define different things and the question asks something different. $\endgroup$
    – Sam Ezeh
    Jan 10, 2023 at 12:12

1 Answer 1

1
$\begingroup$

#1 looks good, but check a textbook for a formal, precise definition.

None of the sources you mentioned are authoritative sources for this. If you need a correct definition, you should be consulting a textbook, not Internet sources.

A textbook would be an authoritative source for the definitions of decidability. Wikipedia is not a primary source -- it is a summary, with references to where you can read authoritative sources. So, in case of any doubt, go to an authoritative source. For technical matters, Wikipedia is often pretty good, but it's not perfect. A random answer on the Internet is not an authoritative source.

And in this case, for #2, you have not correctly quoted the answer. You left out a key part of the answer (the limit on the number of steps of its execution). I think part of the problem is that the answer you link to in #2 was answering a different question (about polynomial-time algorithms), and gave an answer tailored to that other question. I imagine you tried to adjust what was actually written there to your actual question (by omitting the part of the answer that refers to limits on the number of steps of execution), in hopes that this would give an appropriate version suitable for your question, but your adjustment was faulty and is not the correct way to generalize what they wrote to your situation. In other words, in #2, you've created a self-inflicted problem in the way you tried to modify what you read elsewhere to make it applicable to your situation.

For instance, a Turing machine that halts and accepts for all $x \in A$, but fails to halt for some (or all) $x \notin A$, would not qualify as a valid decider for $A$.

$\endgroup$
4
  • $\begingroup$ Thanks for the clarification, but I am still not sure how the answer in #2 make sense. Let "decide if a program halts in polynomial time" be problem HP. It satisfies definition in answer #2, but I feel it's at least as hard as halting problem, hence should not be solvable ... $\endgroup$
    – xade93
    Jan 10, 2023 at 6:15
  • $\begingroup$ @xade93, I don't understand what you are asking, but it sounds like a separate question. It sounds like you are reading cs.stackexchange.com/q/1245 and trying to reason by analogy about what the definition of decidability should be. That is likely to be confusing. I suggest that you don't try to guess/infer what the definition must be based on that other question, and instead consult an authoritative source about what the exact definition actually is. cs.stackexchange.com/q/1245 is asking a different question, so the answers there will be different. $\endgroup$
    – D.W.
    Jan 10, 2023 at 6:43
  • $\begingroup$ Alternatively, if your actual goal is to understand that answer there, then you should handle that by leaving a comment there or asking a new question about understanding that answer. But this question on this page asks for the definition of decidability, which isn't the same as what that other question is discussing. $\endgroup$
    – D.W.
    Jan 10, 2023 at 6:45
  • $\begingroup$ Thanks, I don't have enough stackexchange reputation now to comment on that post. Guess my problem is I lack systematic study so have too many gaps to fill to make sense. I will try to follow some book in the topic. Thanks $\endgroup$
    – xade93
    Jan 11, 2023 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.