2
$\begingroup$

Let $P=\{L \mid \exists w\in \Sigma^* s.t. w\in L \wedge \forall z>w\colon z\in L\}$ .

Now denote $L=\{\langle M \rangle \mid L(M) \in P \}$.

That is, $L$ is the set of all TMs $M$ s.t. there exists a $w\in \Sigma^*$ s.t. $w$ is accepted by $M$ and for each $z>w$, $z$ is accepted by $M$ as well.

I am trying to find out whether $L$ is in $RE$ or not.

I can easily show that $L$'s complement is $\notin RE$ using Rice's Theorem. But here, if using Rice's Theorem, I can only show that $L \notin R$, but I have no guarantee over $RE$.

I thought about using reduction - either to prove $L\in RE$ or to disprove, but none came about. I thought about using $L_{acc}$ or its complement, $L_{\Sigma^*}$, but could not come up with an idea that will work for either direction of the reduction.

Could someone assist?

$\endgroup$
11
  • $\begingroup$ The complement of an undecidable language is also undecidable. You are confusing decidable languages with recursively enumerable languages. $\endgroup$ Jan 29, 2017 at 22:18
  • $\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 29, 2017 at 22:39
  • $\begingroup$ Yes, I mean recursively enumerable. I've edited the question. $\endgroup$
    – Eric_
    Jan 30, 2017 at 8:21
  • 1
    $\begingroup$ Try reducing the complement of the halting problem to $L$. $\endgroup$ Jan 30, 2017 at 8:55
  • 1
    $\begingroup$ @Eric_ It depends on how you fill the dots. Remember we are checking "halting within k steps" with k given. So the test is decidable, and we are free to swap the then/else branches as wanted. $\endgroup$
    – chi
    Jan 30, 2017 at 12:59

1 Answer 1

1
$\begingroup$

Thanks to @Yuval and @chi, I've been able to find a working reduction.

The reduction is $\overline{L_{halt}} \leq L$. For an input $<M><w>$ we build the following TM $N_w$:

  1. Runs $M$ on $w$ for $k$ steps, where $k$ is the length of the input for $N_w$.
  2. If $M$ was able to accept or reject $w$ within $k$ steps in the above simulation, $N_w$ will reject. Otherwise, accept.

This way, if $<M><w>\in \overline{L_{halt}}$ then $M$ does not halt on $w$ for any length $k$, thus $N_w$ will accept every string. Then, $L(N_w)=\Sigma^*\in P$ and $<N_w>\in L$.

Else, if $<M><w>\notin \overline{L_{halt}}$ then a $n\in\mathbb{N}$ exists s.t. $M$ halts on $w$ within $n$ steps. Thus, for all inputs of length $\geq n$ the TM $N_w$ will reject, and it will only accept inputs of length $ < n$, and not satisfaying the property $P$. Hence, $<N_w>\notin L$.

And since $\overline{L_{halt}}\notin RE$, it follows that $L\notin RE$ as well.

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