chapter, unless otherwise stated, do not contain λ. It is a trivial matter to restate
everything so that λ is included, but we will leave this to the reader.
11.1 Recursive and Recursively Enumerable
Languages
We start with some terminology for the languages associated with Turing
machines. In doing so, we must make the important distinction between
languages for which there existsan accepting Turing machine and languages for
which there exists a membership algorithm. Because a Turing machine does not
necessarily halt on input that it does not accept, the first does not imply the
second.
Definition 11.1
A language L is said to be recursively enumerable if there exists a Turing
machine that accepts it.
This definition implies only that there exists a Turing machine M, such that,
for every w ∈ L,
with q f a final state. The definition says nothing about what happens for w not in
L; it may be that the machine halts in a nonfinal state or that it never halts and
goes into an infinite loop. We can be more demanding and ask that the machine
tell us whether or not any given input is in its language.
Definition 11.2
A language L on Σ is said to be recursive if there exists a Turing machine M that
accepts L and that halts on every w in Σ + . In other words, a language is recursive
if and only if there exists a membership algorithm for it.