# How Universal Turing Machines can do something if a machine doesn't accept?

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.

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

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$$.
• 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$?
• 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. Jan 19, 2022 at 18:23