Next: A r.e, non-recursive language: Lu
Up: A non-r.e. language: Ld
Previous: acceptance table
Suppose that some TM Mj accepts Ld. In that case, entry (j,j)
must be zero by definition of Ld. This means that wj is not in
L(Mj), which contradicts L(Mj)=Ld. Likewise, if entry (j,j)
is one, then wj is not in Ld, which contradicts L(Mj)=Ld.
Therefor, Ld is not r.e.
root
6/10/1998