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.


  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Jan 26 '17 at 19:42
  • $\begingroup$ 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! $\endgroup$ – Raphael Jan 26 '17 at 21:10
  • $\begingroup$ IIRC, universality is undecidable even for NPDAs... $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.