Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank for your post. I have just found a typo in my post. The language USELESS' is "undecidable". I still think that USELESS is undecidable also. –  Petch Puttichai Sep 10 '13 at 15:30
    
Then can you explain precisely what you mean by a "useless state" ? because if it means that the state is never reached, it is decidable. –  Denis Sep 10 '13 at 16:55
    
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
    
You're right in fact it's undecidable, I change the answer. –  Denis Sep 10 '13 at 23:47
    
I agree with your answer. Thank you very much. :) –  Petch Puttichai Sep 11 '13 at 4:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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