next up previous contents
Next: Rice's Theorem Up: A r.e, non-recursive language: Lu Previous: A r.e, non-recursive language: Lu

The Universal Language

The universal language Lu is defined as the set $\{<M,w\gt\vert M$ accepts $w\}$. 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).


root
6/10/1998