Semidécidable

Semidécidable is a term used in computability theory and theoretical computer science. A problem is called semidécidable if there exists an algorithm that, for any instance of the problem where the answer is "yes", will eventually halt and output "yes". However, if the answer is "no", the algorithm may either halt and output "no", or it may run forever without halting. Another way to describe a semidécidable problem is that the set of all "yes" instances is a recursively enumerable set.

The concept is closely related to decidability. A problem is decidable, or recursive, if there is an algorithm that halts on all inputs and correctly determines the answer for every instance. If a problem is decidable, it is also semidécidable, because the halting algorithm for decidable problems will naturally halt and give the correct answer in both "yes" and "no" cases. However, the converse is not true; not all semidécidable problems are decidable.

A classic example of a semidécidable problem that is not decidable is the Halting Problem. The Halting Problem asks whether a given program will halt on a given input. For programs that do halt, we can write an algorithm that will eventually stop and report "yes". But for programs that run forever, no such algorithm can exist that is guaranteed to halt and report "no" for all such cases. Therefore, the Halting Problem is semidécidable but not decidable.