# Prove Undecidability: TM M enters each of its states on Input W?

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?

• – Raphael May 13 '15 at 8:28

## 1 Answer

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.

• I am trying to use Rice theorem for non-trivial properties. Can it be applied to the problem here? Thanks for the response. – levi May 14 '15 at 21:26