11
$\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.

Improve this question
$\endgroup$
3
  • $\begingroup$ In the future, please include your attempts in the question! $\endgroup$
    – Raphael
    Commented Mar 22, 2012 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
    Commented Mar 22, 2012 at 13:38
  • $\begingroup$ No, I meant just include it in the question if there are specific points where you are uncertain. $\endgroup$
    – Raphael
    Commented Mar 22, 2012 at 14:38

2 Answers 2

Reset to default
13
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ ..and since the Halting problem is undecidable, this problem is undecidable as well, correct? $\endgroup$
    – BrotherJack
    Commented Mar 22, 2012 at 0:41
  • $\begingroup$ Indeed, this is correct. $\endgroup$
    – Ran G.
    Commented Mar 22, 2012 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What is the meaning of turning a TM into a PDA with a relaxed stack? $\endgroup$
    – Ran G.
    Commented Mar 22, 2012 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.
    Commented Mar 22, 2012 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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