0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Possible duplicate of Proving ALLTM complement not recognizable $\endgroup$
    – fade2black
    Jun 14 '17 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 '17 at 0:24
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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