# A Question relating to a Turing Machine with a useless state

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.

• In the future, please include your attempts in the question! – Raphael Mar 22 '12 at 6:54
• @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. – BrotherJack Mar 22 '12 at 13:38
• No, I meant just include it in the question if there are specific points where you are uncertain. – Raphael Mar 22 '12 at 14:38

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.

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

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.

• What is the meaning of turning a TM into a PDA with a relaxed stack? – Ran G. Mar 22 '12 at 16:28
• 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$. – Ran G. Mar 22 '12 at 16:29