Next: TMs always halt for
Up: Recursively Enumerable Languages
Previous: Enumeration means listing only
However, just because a TM can generate all the strings in a
r.e. language does not mean that a TM can determine if a particular
string is a member of the language. The class of r.e. languages
include some languages for which it is impossible to mechanically
determine membership, i.e. , if L(M) is such a language, then
any TM recognizing L(M) must fail to halt on some input not in
L(M) [Hopcroft, p. 150].
root
6/10/1998