[Overview] [Previous] [Next]

Recursive and Recursively Enumerable Languages

Remember that there are three possible outcomes of executing a Turing machine over a given input. The Turing machine may

A language is recursive if there exists a Turing machine that accepts every string of the language and rejects every string (over the same alphabet) that is not in the language.

Note that, if a language L is recursive, then its complement -L must also be recursive. (Why?)

A language is recursively enumerable if there exists a Turing machine that accepts every string of the language, and does not accept strings that are not in the language. (Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop.)

Recursive languages are recursively enumerable Clearly, every recursive language is also recursively enumerable. It is not obvious whether every recursively enumerable language is also recursive.

Note on terminology: Turing machines aren't "recursive." The terminology is borrowed from recursive function theory (Turing machines are equivalent to general recursive functions). The terms really don't make sense in this context, so don't worry about trying to make them make sense.


Copyright 1996 by David Matuszek
Last modified Apr 1, 1996