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

- Halt and accept the input;
- Halt and reject the input; or
- Never halt.

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.)

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