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!
I think you'll find the answer is actually that it's undecidable. Why? Well this would let you solve the halting problem.
You are given a TM M and an input x and an oracle Q for the problem you describe. Can we solve the halting problem for M with input x using oracle Q?
First, we connect a new TM N to the front of M. Here's what N does: - deletes the tape contents - writes x onto the tape
M halts on x iff NM halts on all inputs. This should be easy to see since N leaves the tape exactly as M would have seen if the input had been x. We can design N in such a way that all states of N are visited.
Now, modify M into M' by adding a second tape. The second tape will be used to keep track of the highest-numbered state of M' we have visited. Add transitions to M' which read the nth state from the secondary tape and cause M' to transition to the (n+1)st state. The transition from the highest-numbered state of M' should return to the initial state of M' and write something like "finished" on the secondary tape. When M' sees "finished" on the secondary tape, it behaves just like M did and only considers the primary tape.
So M' does exactly what M' does, except that it first visits all the states of M and then resets after which it behaves just like M.
M' halts on x iff M halts on x. Also NM' halts iff M halts on x.
Finally we're ready for the proof. The oracle Q accepts NM' iff M halts on x. Q accepts NM' if NM' accepts an input y that causes NM' to visit all states. But: - all inputs y cause NM' to visit all states (since all states of N are visited by construction, and all states of M' are visited by modification of M); so Q is really just answering the question "does NM' accept any strings?" - NM' erases y from the input tape, writes x and hands it off to M'. So the input y doesn't matter; if NM' accepts any input, it accepts all of them. And it accepts all of them if M' accepts x. - M' accepts the same language as M.
So Q applied to NM' does indeed tell us if M halts on x. Then Q solves the halting problem.