semidecidability

Semidecidability, commonly called recursive enumerability (RE), is a property of a decision problem or language L ⊆ Σ* indicating that there exists a Turing machine which, given an input x, halts and accepts if x ∈ L and may either reject or run forever if x ∉ L. In other words, L is recognizable by a Turing machine, or equivalently, L is the domain of a partial computable function.

Equivalent characterizations include that there is a Turing machine that enumerates the elements of L, or that L is the set of inputs for which some computation halts with acceptance. RE can also be viewed as the class of languages for which there exists a computable procedure that outputs the elements of L one by one.

Relation to decidability: a language is decidable if there exists a Turing machine that halts on every input and always decides yes or no. A language is decidable precisely when both it and its complement are semidecidable. Thus, decidable problems are exactly those that are RE and co-RE.

Examples: The Halting problem H = {⟨M⟩ | M halts on input ⟨M⟩} is semidecidable but not decidable; a universal simulator can detect halting in a dovetailed fashion and accept, but there is no algorithm that decides halting for all inputs. The complement of H is not semidecidable.

Closure properties: RE languages are closed under union, concatenation, and Kleene star, and under intersection with decidable languages, but are not closed under complement. Semidecidability plays a central role in computability theory, illustrating a broad spectrum between decidable and fully noncomputable problems.