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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Possible duplicate of Proving ALLTM complement not recognizable $\endgroup$– fade2blackJun 14, 2017 at 23:14
-
2$\begingroup$ 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. $\endgroup$– D.W. ♦Jun 15, 2017 at 0:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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 $<M_1>$ $\in$ ALL$_{TM}$ then $<M_2>$ is too.
- if $<M_1>$ $\notin$ ALL$_{TM}$ then $<M_2>$ 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.
$\begingroup$
$\endgroup$
You can reduce from $H_{TM}$:
For input $<M,w>$ return (the encoding) for a machine $M_ {M,w}$ such that on input $x$:
Simulate $M(w)$
$Accept$
It’s easy to show $M_{M,w} \in ALL_{TM} \leftrightarrow <M,w>\in H_{TM}$
