Semidécidible

Semidécidible is a term used in computability theory and theoretical computer science to describe a type of formal language. A language is semidécidible if there exists an algorithm, specifically a Turing machine, that will halt and accept any string that is a member of the language, but may either halt and reject or run forever if the string is not a member of the language. This is in contrast to a decidable language, for which the algorithm must halt and reject for strings not in the language.

The concept of semidécidible languages is closely related to the Halting Problem, which is famously undecidable. The Halting Problem asks whether a given Turing machine will halt on a given input. The set of all pairs of (Turing machine, input) for which the Turing machine halts is a semidécidible language, but not a decidable one.

Another way to think about semidécidible languages is in terms of enumerability. A language is semidécidible if and only if it is recursively enumerable, meaning there exists a Turing machine that can enumerate all the strings in the language. For strings not in the language, the enumerator may never reach them.

The class of semidécidible languages is a fundamental concept in understanding the limits of computation and the properties of formal systems. Many important problems in computer science, such as the validity of a logical formula in first-order logic, are semidécidible.