# Is this language recursively enumerable?

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?

• The complement of an undecidable language is also undecidable. You are confusing decidable languages with recursively enumerable languages. Jan 29, 2017 at 22:18
• 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! Jan 29, 2017 at 22:39
• Yes, I mean recursively enumerable. I've edited the question. Jan 30, 2017 at 8:21
• Try reducing the complement of the halting problem to $L$. Jan 30, 2017 at 8:55
• @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.
– chi
Jan 30, 2017 at 12:59

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.