If you want to make money online : Register now

[Solved]: Prove whether this problem is decidable or undecidable

, , No Comments
Problem Detail: 

So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state.

I convinced myself that this problem is decidable, but I am having trouble proving so. A rough outline of my answer would be : Assume we have a TM T that has only one halting state, and if it wants to go through all the states it needs to pass through this halt state and we somehow need to show how they cycle through all the states as such.

Any help would be beneficial, thanks!

Asked By : vampyfreak

Answered By : Ran G.

I believe that you ask whether the following language is decidable:

$$L_{\text{visit all}} = \{ \langle M,w\rangle \mid \text{ $M$ run on $w$ visits all its non-halting states}\}$$

I believe this language is undecidable. The reason is similar to the reason why the following language is undecidable: $$L =\{ \langle M,w\rangle \mid \text{$M$ visit the state $q_1$ when running $w$}\}$$ Very iformally: You can see it by "designating" one state to be special, so if we reach it, it means acceptance. Then reaching all states is equivalent to halting problem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56453

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback