Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$?
How to prove that the problem is undecidable?
I was trying to prove undecidability by Rice's theorem which states that languages having non-trivial property are undecidable. But how can I adjust the problem to the theorem?
Hint. We can assume that a Turing machine has exactly one halting state. If a TM visits all of its states, it certainly visits the halting state. Now figure out a way to modify Turing machines so that, if they do halt, they cycle through all their states just before doing so. This gives you a class of TMs that visit every state if and only if they halt.
