semidecidable

Semidecidable is a term from computability theory describing a class of languages that can be recognized by a Turing machine in one direction. A language L over a finite alphabet is semidecidable (also called recursively enumerable or Turing-recognizable) if there exists a Turing machine M such that, for every string w, M halts and accepts when w is in L, and M may either halt and reject or run forever when w is not in L.

Equivalently, a language is semidecidable if it can be enumerated by a Turing machine. In other words, there is an algorithm that outputs all and only the strings in L (though it may print some strings repeatedly and may not terminate). Semidecidability is also characterized as the existence of a partial computable function whose domain is exactly L.

Semidecidable languages sit between decidable and non-semi-decidable problems in computability. If a language is semidecidable and its complement is also semidecidable, then the language is decidable. Many natural problems are semidecidable but not decidable. A classic example is the Halting problem, which is semidecidable because there is a program that halts and accepts precisely when a given machine halts on a given input, but the problem is not decidable in general.

Closure properties of semidecidable languages include being closed under union, intersection, concatenation, and Kleene star. They are not closed under complementation, so the complement of a semidecidable language need not be semidecidable.

In summary, semidecidable languages are those for which membership can be confirmed by a terminating process, while non-membership may cause non-termination; they are central to the study of computability and undecidability.