An Introduction to Formal Languages and Automata, 7th Edition

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 exists an 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,

$$q_{0}w{\stackrel{\ast }{⊢}}_M{x}_1{q}_f{x}_2,$$

with q_f a final state. The definition says nothing about what happens for w not in L