next up previous contents
Next: TMs always halt for Up: Recursively Enumerable Languages Previous: Enumeration means listing only

Some r.e. languages have no always-halting TM

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