** Next:** Rice's Theorem
** Up:** A r.e, non-recursive language: L_{u}
** Previous:** A r.e, non-recursive language: L_{u}

The universal language *L*_{u} is defined as the set accepts
. This language is recursively enumerable, but not recursive.
This is because a TM can be constructed which, when given <*M*,*w*>
will run *M* on *w*, and will accept if and only if <*M*,*w*> is in
*L*_{u}. The language is not recursive because no TM can decide if
<*M*,*w*> will ever halt (the classic halting problem).

*root*

*6/10/1998*