decidability

Question

E={<M> | M is a TM and L(M)=Φ}. Is E Turing-recognizable?

Comments

not R.E

---

@Sachin why E is not recursive enumerable

Answer 1

Another way to prove E is not RE:

To prove certain language is Turing reconizable or not following step is need to do:
 1. Select any Turing reconizable language like here I am taking
   ATM{<M,w> | M is a TM and M accept w}
 2.Find the reduction function from ATM to the complement of given language E.

 If we able to find a reduction then E is not Turing Reconizable.

The reduction Function(TM F):
  F =   "On input <M,W> where M is a encoding of TM and w is a string"
        1. Construct a new TM M'

           M' = "On input x where x is string"
                a. if x!=w "reject"
                b. else RUN ATM on x ,if ATM "accept" then "accept" else "reject"
        2. Output M'.

[ So, Basically M' is a TM which may accept language consisting of 'w' only or its a empty language. So we can feed M' to E , if E accept that mean w is present in the language which indirectly imply ATM accept w]

So, ATM <m E'
  ===> ATM' <m E but we know ATM' is not Turing Reconizable because ATM is undecidable and ATM is Turing Reconizable.
   So, E is not Turing Reconizable.

Note: E' is Turing Reconizable and E is Undecidable.

Answer 2

E is a language, to accept language E we construct a Turing Machine. Suppose we create a Turing EM for the language E.

EM will be provided as input the encoding of another Turing machines, If that inputted machine M accepts an empty language then it will be a member of language E, else it will be not a member of language. 

Suppose we have a Turing Machine M, we need to check if it accepts an empty language. Turing Machine EM have M and strings eps, a, b, aa, bb, ..... EM will check if M can reach a final state for at least on a single input, and if it accepts at least a single input it will be discarded and not included in language E.
Now, see a possibility T.M M gets into a loop so M will keep on running and we couldn't decide whether it can accept or can't accept anything.
Hence, this given language E is NOT RE.

PS: I think the complement of this given Language E will be RE.

Comments

Definition of E complement will be.

$\bar{E}$ ={<M> | M is a TM and L(M) $\neq$ Φ}.

Now if any string present in L(M) then M will be present in $\bar{E}$. To check it we simulate M on the input $\epsilon$, a, b, aa, ab, so on.....

If any input actually present in L(M) then M will accept it in the finite amount of time. And we can output yes.

In this way, we simulate all the TM and if they really accept some input then they will definitely halt in finite time. And we can say that it will be present in $\bar{E}$.

Yes, $\bar{E}$ is RE.