Empty Language L_e

Empty Language L_e

by YOUSSEF BEN KHALIFA -
Number of replies: 2

Greetings,

I had a question regarding the empty language L_e: from the discussion we had we proved that L_e is not in RE, given that is complement L_ne (non-empty language) is in RE, therefore L_e cannot be recursive.

But is it no true that i could build a TM M such that L(M) = L_e which always halts? More,  precisely, wouldn't be sufficient to build M so that it would reject any string given as input?  

In reply to YOUSSEF BEN KHALIFA

Re: Empty Language L_e

by Giorgio Satta -

What you have just done is writing a TM M that accepts the empty language. This is very easy indeed.

However L_e is something very different. L_e is the set of strings that represent encodings of TMs that accept the empty language. So the encoding of M above will appear in L_e somewhere, together with many other encodings, infinitely many actually.

Writing a TM that recognises L_e is not possible.