Turing Machine Decidability

Question

I have been working on this problem for few hours, but haven't been able to come up with a solution : Is the following problem decidable? Given a TM M, whether there is a w such that M enters each of its states during the computation on w.

I tried to use reduction to show that it's not, but couldn't come up with anything. I also thought in the direction that it's decidable, but there wasn't any finite number of configuration from which I could give the time bound.

Any help will be appreciated.

Answer 1

No, it isn't decidable. I think that probably follows from Rice's theorem, but it's possible to build a proof without it.

Shannon proves that for every Turing machine there is a two-state Turing machine which simulates it. By adding a couple of characters to the alphabet and a couple of setup states which guarantee that they will be on the tape, we can ensure that the two "core" states are both visited before the calculation proper begins. We can then add a "Halt" state and replace halt transitions in the "core" two-state machine with transitions to the "Halt" state. Thus our constructed machine visits each of its states iff the original machine halts.

Suppose that we can decide whether there exists an input $w$ on which a TM $M$ halts. Then we can decide the halting problem: given TM $M'$ and input $w'$ and asked whether $M'$ halts on input $w'$ we can build a machine $M$ which discards its input, sets up $w'$ on the tape, and simulates $M'$.

Answer 2

I think you can reduce halting problem to this without using elaborate results. Say you start from any TM $M$ with a state $q_{stop}$. The other states are $q_0,q_1,\dots,q_n$. You can build the Turing machine $M'$ which simulates $M$, but has one more symbol $X$ in the alphabet. When $q_{stop}$ is reached, the machine $M'$ goes to the right of the band, reaches the first blank symbol, and write its new symbol $X$. It does this with a new state $q'$. Then, $M'$ has transitions labeled by $X$ : $q'\to q_0\to q_1\to\dots\to q_n\to q_{stop}'$, where $q_{stop}'$ is a new state, and the stop state of $q'$. In total, $M'$ has the states of $M$ plus two new states: $q'$ and $q_{stop}'$, and $M'$ visits all states on $w$ iff $M$ stops on $w$. Therefore, your problem is undecidable.