title: "Turing-Recognizable Language"

Turing-Recognizable Language

Definition. A language $A$ is Turing-recognizable if $A = L(M)$ for some Turing machine $M$, that is, if $M$ accepts exactly the strings in $A$. On strings not in $A$, $M$ may reject or may run forever.

The permission to run forever is the whole difference from decidable. Every decidable language is Turing-recognizable; the converse fails, as Lecture 7 shows with the halting problem. A language is Turing-recognizable exactly when some enumerator prints it, and if both $A$ and its complement are Turing-recognizable then $A$ is decidable, proved by running the two machines in parallel. Also called recursively enumerable in older sources.