1
$\begingroup$

I read that the following language is r.e. but not not-Turing recognizable

$L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs

I am not sure why it is not not-Turing recognizable., since I could perhaps make the following reduction from $\overline{A_{TM}}$ to $L$ given this procedure $R$ namely:

$R$: On input $<M,w>$:

  1. Construct TM $M_1$, where on input $x$, if $x=1$, accept
  2. If input $x$ is not equal to $1$, run $M$ on input $w$ for $|x|$ steps. If after $|x|$ steps, $M$ does not accept $w$, then accept $x$

From this reduction, if $M$ does not accept $w$, i.e. $<M,w> \in \overline{A_{TM}}$, then $M_1$ accepts any input word, i.e. $M_1 \in L$.

Am I missing something here?

$\endgroup$

1 Answer 1

3
$\begingroup$

What you are missing is that if $\langle M, w\rangle \notin \overline{A_{\mathrm{TM}}}$, i.e. if $M$ halts on input $w$, you don't know whether or $M_1 \notin L$. If $M$ does halt on $w$, but this takes longer than $20$ steps, it would also hold that $M_1 \in L$. Thus, you don't have a reduction here.

That the language $L$ cannot be co-RE is an immediate consequence of Rice's theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.