Skip to main content

Questions about which problems are semi-decidable, also known as computably enumerable, Turing recognizable or recursively enumerable.

A problem $L$ is decidable if there is an algorithm which, given an input $x$, halts and output whether $x \in L$ or not. In contrast, a problem $L$ is semi-decidable if there is an algorithm which, on input $x$, halts if $x \in L$, and runs into an infinite loop if $x \notin L$.

The quintessential example of a semi-decidable problem which is not decidable is the halting problem.