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?

  • $\begingroup$ The complement of an undecidable language is also undecidable. You are confusing decidable languages with recursively enumerable languages. $\endgroup$ – Yuval Filmus Jan 29 '17 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 '17 at 22:39
  • $\begingroup$ Yes, I mean recursively enumerable. I've edited the question. $\endgroup$ – Eric_ Jan 30 '17 at 8:21
  • 1
    $\begingroup$ Try reducing the complement of the halting problem to $L$. $\endgroup$ – Yuval Filmus Jan 30 '17 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 '17 at 12:59

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.


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.