next up previous contents
Next: A r.e, non-recursive language: Lu Up: A non-r.e. language: Ld Previous: acceptance table

The language Ld is not r.e.

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.