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.
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.