# Determine whether a TM visits each of its states exactly once during computation

(Decidable or not?) Formulate the following problem as a language: Given a Turing machine $M$ and a string $w$, determine whether $M$ visits each of its states exactly once during the computation with input string $w$. Prove your answer.

So the problem above is what I am trying to solve. I am looking for a general direction to solve this so far this is what I am thinking but I may be completely wrong.

My Thoughts: This problem is decidable because the Turing machine can have a list of all possible paths ,$E^*$, and we could check $E^*$ to ensure that each state was visited once and only visited once within the computation. However this doesn't seem like nearly enough and I am not sure what direction to head.

• Given a Turing machine, M, that has multiple states, m, we know that if M terminates after m steps then it has visited every state exactly once. If we take another machine M’ that takes on a pair (M,w) where M is a Turing machine and w is the input that M takes on. We can simulate M on M’. We run M on w and in doing so we can count the number of states that it visits. M’ job is to determine whether the number of states visited is equal to m. If it is equal to m then accept, if it is not equal to m then reject. my question now is would this be enough to prove that this is decidable Dec 2 '16 at 22:13

Hint: If a Turing machine has $m$ states and it visits each of them exactly once, then it terminates after $m$ steps.