World's most popular travel blog for travel bloggers.

[Solved]: Is the following language recursively enumerable?

, , No Comments
Problem Detail: 

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

Asked By : Marik S.

Answered By : chi

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52440

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback