# Proof of undecidability of $FINITE_{\text{TM}}$ and $USELESS_{\text{TM}}$

I came across these 2 problems about proving of undecidability of languages:

$1$. $FINITE_{\text{TM}} = \{\langle M \rangle | M \text{ is a Turing machine and } L(M) \text{ is a finite language} \}$.

For this problem, I think if I use Rice's theorem, the result of undecidability follows immediately (doesn't it?). However, I want to do it in the different way. Since all finite languages are regular, I think may be I can make use of the fact that $$REGULAR_{\text{TM}} = \{\langle M \rangle | M \text{ is a Turing machine and } L(M) \text{ is a regular language} \}$$ is undecidable. I tried using mapping reduction but still cannot go further and arrive at the result I want.

$2$. $USELESS_{\text{TM}} = \{ \langle M \rangle | M$ is a TM that has at least one useless state $\}$.

While I thought about this problem, I got an idea of another language, $$USELESS'_{\text{TM}} = \{ \langle M, q \rangle | M \text{ is a TM and } q \text{ is a useless state of } M \}.$$ For $USELESS'_{\text{TM}}$, I can prove its undecidability easily by using a mapping reduction from $E_{\text{TM}} = \{ \langle M \rangle | M \text{ is a TM and } L(M) = \phi \}$. I think there must be a way to relate $USELESS_{\text{TM}}$ to $USELESS'_{\text{TM}}$. However, again, I cannot arrive at the result that $USELESS_{\text{TM}}$ is undecidable.

Do you have any suggestion or comment?

Thank you very much.

-

For 1., you're right that it follows directly from Rice theorem. Reduction to REGULAR seems hard to do: you would have to build a machine $M'$ from a machine $M$, such that $L(M')$ is finite if and only if $L(M)$ is regular.
For 2., any machine can be turned into a machine with 1 accepting state, and then deciding whether this state is reachable is the same as deciding whether $L(M)\neq\emptyset$. So it shows that USELESS' is undecidable. Then, you can show that USELESS is also undecidable in the following way:
The useless state is a state that is never entered by any input string. But if USELESS' can be decided by a machine U, we can use U to construct a machine for deciding $E_{TM}$ which is known to be undecidable. Hence, there is a contradiction. I wonder that can we really determine that a state is reachable or not by just looking at the transition graph? – Petch Puttichai Sep 10 '13 at 17:13