Decidability & Recognizability

closure of the decidable languages

When we say a class of languages is 'closed under' an operation, we mean: take any languages from the class, combine them with that operation, and the result is still in the class — the class is a sealed room that those operations cannot break you out of. The decidable languages are wonderfully well-behaved this way. Because a decider always halts, you can run deciders, read off their definite yes/no answers, and freely combine those answers with ordinary logic — and the combined machine still always halts.

Concretely, the decidable languages are closed under all the usual operations: complement, union, intersection, concatenation, and the Kleene star. Complement is the cleanest illustration: given a decider for L that always halts, just swap its accept and reject states; the result always halts and accepts exactly the non-members, so the complement is decidable. Union and intersection: run the two deciders one after the other (both finish), then accept on 'either' for union or on 'both' for intersection. Concatenation of L1 and L2: to test w, try every way to split w into a first part u and a second part v (there are only |w|+1 splits, a finite list), run the L1-decider on u and the L2-decider on v, and accept if any split works. Star is similar with all finite ways to chop w into pieces. Every step is a finite amount of work on top of always-halting deciders, so the result always halts.

The headline is that the decidable languages form a Boolean-algebra-friendly, fully symmetric class — and the symmetry under complement is the crucial contrast with the recognizable class. Because a decider gives a guaranteed answer in both directions, flipping yes and no is harmless. The recognizable languages do NOT enjoy this: they are closed under union, intersection, concatenation, and star, but NOT under complement, precisely because a recognizer can loop and you cannot safely flip a 'loops forever' into a clean 'reject'. That single asymmetry is the fingerprint of the loop-forever possibility.

If L1 = {even-length strings} and L2 = {strings of a's} are both decidable, so is their intersection {even-length strings of a's}: run both deciders (each halts) and accept only if both accept. Complement of L1 (the odd-length strings) is decidable too — just flip accept and reject.

Always-halting answers can be flipped and combined freely, including complement.

The make-or-break property is closure under COMPLEMENT. Decidable languages have it (flip a decider); recognizable languages do not, because you cannot turn a possible infinite loop into a clean reject.

Also called
closure properties of recursive languageswhat decidable languages are closed under遞迴語言的封閉性