next up previous contents
Next: Decidability Up: Are All Languages Recursively Previous: Are All Languages Recursively

Some languages not r.e.

No. All languages are not recursively enumerable. This is not surprising, since the set of recursively enumerable languages is the same as the set of languages accepted by TMs, which we have previous said is equivalent to the set of procedures. Just as some functions have no corresponding procedure, some languages cannot be accepted by a TM.