Next: Rice's Theorem
Up: A r.e, non-recursive language: Lu
Previous: A r.e, non-recursive language: Lu
The universal language Lu 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
Lu. The language is not recursive because no TM can decide if
<M,w> will ever halt (the classic halting problem).