# Which definition of decidable is correct?

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.

• 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. Jan 10, 2023 at 12:12

#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.

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$$.