[Math] Proof of undecidability of $FINITE_{\text{TM}}$ and $USELESS_{\text{TM}}$

computabilityformal-languagesturing-machines

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.

Best Answer

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:

Suppose you have an algorithm for USELESS, then you can always try removing 1 state, until the machine is not in USELESS. If it does not work try 2 states, and so on... This way you will find the set of useless states. If the accepting state is in them, then the machine does not accept anything, otherwise it does. This shows that USELESS is also undecidable.

Related Question