Link Search Menu Expand Document

Turing-recognisable and decidable languages

A language is said to be Turing-recognisable or recursively enumerable, just if it is recognised by some Turing machine.

A language is said to be co-Turing-recognisible or corecursively enumerable, just if its complement is recognised by some Turing machine.

A language is said to be Turing-decidable or recursive, just if it is decided by some Turing machine.

Theorem: A language is Turing-decidable iff it is both Turing-recognisible and Turing-corecognisible.


Table of contents