# Prove ALL$_{\text{TM}}$ is undecidable reduction problem

Given ALL$_{\text{TM}}$ = { < M > | where M is a TM and L(M) = $Σ^*$ } show this is undecidable. I'm also told not to use Rice's theorem. I'm having difficulties with reduction type problems. How would you do a proof for this using a reduction of A$_{\text{TM}}$? Any pointers to resources are much appreciated.

• Possible duplicate of Proving ALLTM complement not recognizable Jun 14 '17 at 23:14
• What searching have you done? There are lots of worked examples here (see the reductions tag), and in standard textbooks. If you want help understanding how to do reductions, I suggest reading standard references -- there would be little point in repeating that material. As for your specific exercise, I don't know whether anyone will be interested in doing the exercise for you. You might find this page helpful in improving your question.
– D.W.
Jun 15 '17 at 0:24

It is possible to show ALL$$_{TM}$$ is undecidable by Rice's theorem.

Where ALL$$_{TM}$$ = {<M>, M is a TM and L(M) = $$\Sigma^*$$}

Take two TMs M$$_1$$ and M$$_2$$ where L(M$$_1$$) = L(M$$_2$$).

Because both recognize the same language,

• if $$$$ $$\in$$ ALL$$_{TM}$$ then $$$$ is too.
• if $$$$ $$\notin$$ ALL$$_{TM}$$ then $$$$ isn't as well.

So they either both have descriptions in ALL$$_{TM}$$, or none of them.

It is non-trivial:

• There trivially exists a TM M$$_1$$ that accepts on all inputs $$w \in$$ $$\Sigma^*$$.
• There trivially exists a TM M$$_2$$ that recognizes $$L(M_2) = \{ab\}$$, which is clearly not in $$\textit{ALL}_{TM}$$

Now, by Rice's theorem, it is proven that ALL$$_{TM}$$ is undecidable.

You can reduce from $H_{TM}$:

For input $<M,w>$ return (the encoding) for a machine $M_ {M,w}$ such that on input $x$:

1. Simulate $M(w)$

2. $Accept$

It’s easy to show $M_{M,w} \in ALL_{TM} \leftrightarrow <M,w>\in H_{TM}$