Decidability & Recognizability

decidable versus recognizable

Think of two kinds of helpdesk. The first one always calls you back with a definite answer, yes or no, every single time — you can plan your day around it. The second one calls you back to say YES whenever the answer is yes, but on a 'no' it sometimes just goes silent and leaves you hanging by the phone indefinitely. Both can confirm a yes. Only the first can also confirm a no. That difference — guaranteed termination versus possible silence — is exactly the gap between decidable and recognizable.

Precisely: a language is DECIDABLE (recursive) if some Turing machine halts on every input and gives the correct accept/reject — a true decision procedure. It is RECOGNIZABLE (recursively enumerable) if some machine accepts exactly the strings in the language but is allowed to loop forever on strings outside it. Every decidable language is recognizable (always-halt is a special case of accept-eventually), but the reverse fails: there exist recognizable languages that are not decidable. The standard witness is A_TM = {(M, w) : M accepts w}, which a universal machine can recognize by simulation yet no machine can decide.

Why insist on the distinction? Because it is the dividing line between 'a computer can in principle solve this with a guaranteed answer' and 'a computer can confirm a yes but might never confirm a no'. In practice that means: for a decidable problem you can write a program and safely wait for it; for a merely recognizable one, your search might run forever on the cases where the answer is no, and you have no way to know whether to keep waiting or give up. The next theorem ties it together: a language is decidable exactly when both it and its complement are recognizable.

Is a given DFA's language empty? Decidable — a finite reachability check always halts. Does a given Turing machine accept a given input? Only recognizable — simulate and accept if it accepts, but if it loops you loop too.

Same surface shape ('does X accept Y?'), opposite fates — the model decides whether it can always halt.

Recognizable is not a 'weaker kind of decidable you can fix by trying harder'. On a non-member input the gap is fundamental: there may be no finite signal at all that the answer is no.

Also called
recursive vs recursively enumerablehalt-always vs maybe-loop可判定與可識別之別