Next: Decidability
Up: Are All Languages Recursively
Previous: Are All Languages Recursively
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.
root
6/10/1998