# Prove whether this problem is decidable or undecidable [duplicate]

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!

• Can you try to phrase more precisely what the problem is? What exactly is the input, what constitutes a YES answer, and what constitutes a NO answer? This is particularly important with "meta" problems: problems which themselves operate on Turing Machines. Apr 25 '16 at 0:11
• The input would be a string that is accepted by the TM, and a YES answer would be there is a string visits every non-halting state and its complement would be there is no such string where the string wouldnt visit every non-halting state Apr 25 '16 at 0:28

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