Let $ L = \{ \langle M \rangle : L(M) = \Sigma^* -\{\epsilon\} \}$, Show that $L\notin RE$

Question

Let $ L = \{ \langle M \rangle : L(M) = \Sigma^* -\{\epsilon\} \}$

Determine whether $ L\in RE, \space L\in R, \space L\in co-RE$, or none of the above.

I tried to show a reduction function from $L_{\Sigma^*}$ to $L$ to prove that $L\notin RE$ , here is my attempt:

$\forall M\in L_{\Sigma^*} : f(M) = M'$, where M' is a Turing machine which works as follows:

$\forall w\in \Sigma^*: $ if $w=\epsilon$ accept w; Otherwise run M on w and answer as M.

I manged to show that if $X \in L_{\Sigma^*}$ than $f(X)\in L$, but the other direction ($X \notin L_{\Sigma^*}$ than $f(X)\notin L$) seems to be more problematic and I'm not sure that reduction will even work.

I will appreciate any direction.

Btw, I'm new to reduction so please try to be patient and understanding.

Thanks!

Answer 1

Hint: Let $L_{\Sigma^*}$ the language of descriptions of Turing machines halting on all inputs. Choose some computable surjective mapping from $\Sigma^+$ to $\Sigma^*$, and use it to reduce $L_{\Sigma^*}$ to $L$. Since $L_{\Sigma^*}$ is neither RE nor coRE, it follows that the same holds for $L$.