Decidability

A problem is decidable when a Turing machine exists that halts on every input and correctly classifies it as a yes-instance or a no-instance.

Formal definition

Let $\Sigma$ be a finite alphabet and $L \subseteq \Sigma^*$ a language. $L$ is decidable iff there exists a Turing machine $M$ such that, for every input string $w \in \Sigma^*$,

Equivalently, the characteristic function

is total computable: some Turing machine, given $w$, outputs $\chi_L(w)$ in finite time for every $w$, with no exceptions.

The class of decidable languages is traditionally denoted $\mathsf{R}$ (or $\mathsf{REC}$). In Kleene’s terminology it is the class of recursive sets, which is why decidable and recursive are synonymous across most of the literature.

Intuition

Decidability is the strictest form of algorithmic tractability that computability theory recognizes. It demands totality: not merely that the algorithm answers eventually on the yes-instances, but that it answers always — on yes-instances, no-instances, and everything in between — without ever looping forever.

This totality is precisely what separates $\mathsf{R}$ from the larger class $\mathsf{RE}$ of recognizable (or recursively enumerable) languages. A recognizer is permitted to loop silently on strings outside the language; a decider must reject them explicitly. The gap between the two is exactly where the halting problem lives: $\text{HALT} \in \mathsf{RE} \setminus \mathsf{R}$. Every decidable language is recognizable, but the converse fails, and it fails specifically because of diagonalization.

Decidability is a property of the language, not of any particular algorithm deciding it. Once some machine is shown to decide $L$, the problem is closed: every other correct decider for $L$ joins the club automatically, regardless of how it works internally. Decidability asserts the existence of a method; it says nothing about any specific method’s cleverness or cost.

Examples

Decidable:

• The empty language $\varnothing$ and the total language $\Sigma^*$. Trivially — the deciders ignore their input.
• Every finite language. A decider hard-codes the membership table and looks up the input in constant time.
• Every regular language. A deterministic finite automaton simulates in linear time, always halts, always decides.
• Every context-free language. The CYK algorithm decides membership in $O(n^3)$ time (Cocke, Younger, Kasami, independently in the 1960s).
• Primality: $\text{PRIMES} \in \mathsf{P} \subseteq \mathsf{R}$. Decidability was elementary long before Agrawal, Kayal, and Saxena showed in 2002 that it is even polynomial.

Undecidable:

• The halting problem $\text{HALT}$ (Turing 1936). The refutes edge on that article traces the diagonal proof.
• Validity in first-order logic — the Entscheidungsproblem Hilbert and Ackermann posed in 1928. Settled independently by Church (1936) and Turing (1936).
• The word problem for finitely presented groups. Novikov (1955) and Boone (1958) showed there is no uniform algorithm to decide whether two expressions represent the same group element.
• Hilbert’s tenth problem — does an arbitrary Diophantine equation admit an integer solution? Undecidable, Matiyasevich 1970, building on Davis, Putnam, and Robinson’s work across the 1960s.
• Post’s correspondence problem (Post 1946), a combinatorial problem on string pairs that reduces from HALT and is the favourite starting point for undecidability proofs in formal language theory.

Notes

The term recursive has nothing to do with recursion as self-reference in programming. It comes from Kleene’s work in the 1930s and 1940s on recursive function theory, where a recursive set is one whose characteristic function is built up from primitive recursion, composition, and the $\mu$-operator. The accidental clash with the programming-language sense of the word is unfortunate enough that modern textbooks increasingly prefer decidable and recognizable over recursive and recursively enumerable — though both pairs remain in active use, especially in proof theory and recursion theory.

By the Church–Turing thesis, decidability is independent of the model of computation. A language decidable by a Turing machine is decidable by a $\lambda$-calculus reduction strategy, by the $\mu$-recursive functions, by a random-access machine, by a Post production system, by any of the other formalisms known to compute the same class. All of them define the same $\mathsf{R}$. This invariance is the essential content of Church 1936 and Turing 1936 taken jointly, and it is why decidability is treated as a property of the problem rather than of any particular piece of machinery.