4
$\begingroup$

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!

$\endgroup$
3
  • $\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$ Jan 26, 2017 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, 2017 at 21:10
  • $\begingroup$ IIRC, universality is undecidable even for NPDAs... $\endgroup$
    – Raphael
    Jan 26, 2017 at 21:11

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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