0
$\begingroup$

In our Computability & Complexity course, we wanted to show that $ALL_{TM}\notin RE$. To do that, we have seen the following claim (I'm summarizing it):

Denote the languages: $ALL_{TM}=\{(M)|L(M)=\Sigma^*\}$ and $A_{TM}=\{(M,\,w)|w\in L(M)\}$.

The problem is that we want to simulate $M$ on $w$, but we can actually want to do something if $M$ does not accept $w$. Now, if $M$ rejects $w$ that's fine. We'll wait until it rejects, and go about our business. However, what happens if $M$ does not halt on $w$? Well, then we need some tricks.

Claim: $\overline{A_{TM}} \le_M ALL_{TM}$ (and thus $ALL_{TM} \notin RE$). Construction: On input $(M,\,w)$, the reduction constructs the machine $K$ that on input $x$, simulates $M$ on $w$ for $|x|$ steps. If, during this, $M$ accepts, then $K$ rejects. otherwise, $K$ accepts.

Then, when proving the correctness, they claimed the following:

If $(M,\,w)\in \overline{A_{TM}}$ then $M$ does not accept $w$ and in particular $M$ does not accept it within $|x|$ steps, for all $x$. Thus, $K$ accepts every input so $L(K)=\Sigma^*$ and $(K)\in ALL_{TM}$.

Now, I understand that, take some input, $(M,\,w)$ from $\overline{A_{TM}}$, then if $M$ rejects/not halt on $w$ it means that $(M,\,w)\in \overline{A_{TM}}$ and otherwise it's not. My problem is with the justification "[...] in particular $M$ does not accept it within $|x|$ steps, for all $x$. Thus, $K$ accepts every input [...]": Lets say that $M$ won't halt on $w$. In this case, when $K$ simulate $M$ - $M$ will not halt - and as a result, $K$ won't halt either, so how come we can say that it'll accept? I understand that in the construction we said that if during the simulation $M$ accepts, then $K$ rejects - but what if in the simulation $M$ doesn't stop at all, how will $K$ have the opportunity to accept? How will it know when to say "enough is enough, I'm going to accept this?"? I can't see what the "trick" is that they applied here.

$\endgroup$
2
  • $\begingroup$ Please briefly define $ALL_{TM}$ and $A_{TM}$ and $K$. Not all sources use the same names. $\endgroup$
    – plshelp
    Commented Jan 18, 2022 at 22:43
  • $\begingroup$ @plshelp Updated it accordingly, thanks. $\endgroup$
    – OzB
    Commented Jan 18, 2022 at 22:49

1 Answer 1

1
$\begingroup$

The input of $K$ is $x$, and $K$ will only simulate $M$ during at most $|x|$ steps. Therefore, there is no situation where the simulation of $K$ does not stop.

If $M$ does not accept $w$, then for any word $x$ of length $n$, executing $M$ during $n$ steps will never reach an accepting state. And so, after $n$ steps of simulation, the TM $K$ will accept the word $x$.

$\endgroup$
3
  • $\begingroup$ Thanks for the explanation! Does it means that we can assume that $|x|$ is arbitrarily big, so no matter in which step $M$ will accept $w$, we will able to reach it as we can choose the length of $x$? $\endgroup$
    – OzB
    Commented Jan 19, 2022 at 18:12
  • $\begingroup$ Note that in the case of your question (and of my answer), $M$ will never accept $w$. But yes, no matter what $x$ we choose, its length will be finite, hence so will be the simulation. $\endgroup$
    – Nathaniel
    Commented Jan 19, 2022 at 18:23
  • $\begingroup$ Gotcha, thanks!! :) $\endgroup$
    – OzB
    Commented Jan 19, 2022 at 18:39

Your Answer

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

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