2
$\begingroup$

Let $L =\{ <M> | $ the amount of words $w\in\Sigma^*$ that $M$ does not halt on is finite $\}$.

I would like to prove that $L\notin RE$.

I can show that $\overline{L}\notin RE $ that is $L\notin CoRE$.

I do this with showing a reduction: $\overline{L_{acc}} \leq \overline{L} $ and since $\overline{L_{acc}}\notin RE$ then $\overline{L}\notin RE$.

The reduction goes as follows:

  • input: $<M>,<w>$
  • output: $<M_w >$

where $<M_w>$ is a TM that, on an input $x$ ignores it and performs:

  1. Run $M$ on $w$
  2. If $M$ rejected get yourself into an inf loop
  3. If $M$ accepted then accepts as well.

Now if $<M><w>\in\overline{L_{acc}}$ then $w\notin L(M)$, thus $M$ either rejects $w$ or does not end its calculation on it, but in both cases $M_w$ will not end its calculation on all inputs. Otherwise, if $<M><w>\notin \overline{L_{acc}}$ then $w\in L(M)$ and then $M_w$ will halt (and accept) its calculation on every input $x$.

So I have that $\overline{L_{acc}} \leq \overline{L} $ and thus $\overline{L}\notin RE$, that is $L\notin CoRE$.

But I am at a loss on how I can prove $L\notin RE$? I tried a reduction from $\overline{L_{acc}}$, but this idea does not work because $M$ might not halt on $w$. I also tried from $L_{\Sigma^*}$ or from $L_d$, but could not find a reduction that will prove me that $L\notin RE$.

Does someone have an idea for such a reduction? Or perhaps another method to prove $L\notin RE$?

$\endgroup$
  • $\begingroup$ Your reduction should be from $\overline{L_{acc}}$ to $L$, rather than to $\overline{L}$. A reduction $\overline{L_{acc}}\le \overline{L}$ is equivalent to $L_{acc}\le L$ and all that would show is that $L$ is at least as "hard" as $L_{acc}$ which we know is RE. See my answer to this question for an applicable technique. $\endgroup$ – Rick Decker Jan 29 '16 at 18:55
3
$\begingroup$

I'll provide some hint. Try building a reduction $\overline{L_{acc}} \leq L$ changing your argument as follows:

... where $<M_w>$ is a TM that, on an input $x$ it performs:

  1. Run $M$ on $w$ for $|x|$ steps
  2. If $M$ rejected within $|x|$ steps ...
  3. If $M$ accepted within $|x|$ steps ...
  4. If $M$ did not halt within $|x|$ steps ...

When $M$ does not accept $w$, you want the above to diverge only on finitely many $x$s.

When $M$ accepts $w$, you want the above to diverge on infinitely many $x$s.


Alternatively, you can try to exploit the Rice-Shapiro theorem.

$\endgroup$

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.