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

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!

• Your problem is $\Pi_2$-complete, and so not in RE or coRE. The language TOT (your $L_{\Sigma^*}$, as far as I can tell) is known to be $\Pi_2$-complete, so it suffices to reduce it to $L$. – Yuval Filmus Jan 26 '17 at 19:42
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Jan 26 '17 at 21:10
• IIRC, universality is undecidable even for NPDAs... – Raphael Jan 26 '17 at 21:11

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$.