10
$\begingroup$

OK, so here is a question from a past test in my Theory of Computation class:

A useless state in a TM is one that is never entered on any input string. Let $$\mathrm{USELESS}_{\mathrm{TM}} = \{\langle M, q \rangle \mid q \text{ is a useless state in }M\}.$$ Prove that $\mathrm{USELESS}_{\mathrm{TM}}$ is undecidable.

I think I have an answer, but I'm not sure if it is correct. Will include it in the answer section.

$\endgroup$
  • $\begingroup$ In the future, please include your attempts in the question! $\endgroup$ – Raphael Mar 22 '12 at 6:54
  • 1
    $\begingroup$ @Rapael Just did. I wrote it up when I did the question, but given my lack of reputation I was unable to post it for at least 8 hours. I'd be interested in knowing if it is a valid answer. $\endgroup$ – BrotherJack Mar 22 '12 at 13:38
  • $\begingroup$ No, I meant just include it in the question if there are specific points where you are uncertain. $\endgroup$ – Raphael Mar 22 '12 at 14:38
12
$\begingroup$

This is clearly reducible from the Halting Problem. If a machine $M$ does not stop on input $x$ then any final state is "useless". Given an input $M,x$ for the Halting problem, it is easy to construct $M_x$ that halts on every input (thus its final state is not useless) if and only if $M$ halts on $x$. That way you can decide Halting Problem if you can decide $\mathrm{USELESS}_{\mathrm{TM}}$, which yields a contradiction.

$\endgroup$
  • $\begingroup$ ..and since the Halting problem is undecidable, this problem is undecidable as well, correct? $\endgroup$ – BrotherJack Mar 22 '12 at 0:41
  • $\begingroup$ Indeed, this is correct. $\endgroup$ – Ran G. Mar 22 '12 at 0:42
2
$\begingroup$

For the purposes of this proof we will assume that $\mathrm{USELESS}_{\mathrm{TM}}$ is decidable to display a contradiction.

Create TM $R$ that does the following:

  • Converts TM $M$ to a pushdown automata $P$ with a relaxed stack (ie. no LIFO requirement). This is equivalent to a directed graph detailing the transition between $M$'s states.
  • Mark the start state of $P$.
  • From the start state commence a breadth-first search along each outbound edge marking each unmarked node.
  • When the search terminates, if there are any unmarked nodes which match $q$, accept; otherwise reject.

Then create TM $S$ = "On input $$

  1. Create TM $R$ as shown above.
  2. Run $q$ on $R$.
  3. If $R$ returns accept, accept; if $R$ rejects, reject"

Thus, if $R$ is a decider for $\mathrm{USELESS}_{\mathrm{TM}}$ then $S$ is a decider for $A_{\mathrm{TM}}$ (the acceptance problem). Since $A_{\mathrm{TM}}$ is proven to be undecidable (see Michael Sipser Theory of Computation Theorem 4.11 on page 174), we have reached a contradiction. Therefore, the original hypothesis is incorrect and $\mathrm{USELESS}_{\mathrm{TM}}$ is undecidable.

$\endgroup$
  • $\begingroup$ What is the meaning of turning a TM into a PDA with a relaxed stack? $\endgroup$ – Ran G. Mar 22 '12 at 16:28
  • 1
    $\begingroup$ Is $R$ the decider assumed to exist? if so - you don't need to describe its action. In fact you can't describe its action, since it doesn't really exists. All you know that it answers yes/no according to whether or not the input is in $L$. $\endgroup$ – Ran G. Mar 22 '12 at 16:29

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.