Is the given problem Undecidable?

Question

Does a TM M have a state that is visited no more than $K$ times when started on an empty tape ?

---

I tried to reduce it to halting problem, but didn't get the right way.

I want to know that is there any other method, it can be solved (except reduction) ?

Answer 1

Suppose you can do that. Take a machine you want to solve halting problem for, replace 'halt' with going to additional halt state and at the beginning cycle through all other states. Run your hypothetical check for this altered machine and $K=0$ and you've solved the halting problem (true means we won't reach halt state since we've visited all other states once in the beginning, false means we will get to halt which only happens in the end).

Answer 2

(NOTE: depending on your turing machine model, "accept" and "reject" may be considered their own state. If we do this, then the problem is decidable and trivial, so I will assumine these are special states that are not under consideration of the problem)

The typical solution for these kind of problems is to construct a TM $T_1$ that will simulate an arbitrary turing machine $T_2$ until it halts, where your property $P$ holds iff $T_2$ does end up halting, thus if we can decide $P$ we can decide halting for arbitrary TM $T_2$.

In these case, we will use the property "visits every state more than $K$ times".

It's easy to ensure that this property does not hold if $T_2$ never halts, just add some state "T_2_HALTED" that we visit after $T_2$ halts. We are simulating $T_2$ until it halts, so we never reach this state if $T_2$ never halts.

Now, we just need to ensure this property does hold for any $T_2$ that halts. In other words, we need some way to visit every state in our turing machine $K+1$ times.

(for simplicity I am going to assume that a TM model that can transition without moving the tape head left or right)

After we visit the "T_2_HALTED" state we need to visit every other state $K+1$ times. We do this by first placing an extra $K+1$ letters in our TM alphabet, $\alpha_0 ... \alpha_k$.

Then add to our transitions for every state other than "T_2_HALTED" that if it sees $\alpha_i$ on the tape for $i < k$, it will transition state to itself and write $\alpha_{i+1}$ on the tape without moving the tape head. If it sees $\alpha{k}$ on the tape, it will transition to another state according to some arbitrary total ordering on the state and write $\alpha_0$ on the tape (but make sure "T_2_HALTED" is the last state on this ordering).

Finally, the rule for "T_2_HALTED" is that if the value on the tape is not any $\alpha_i$, then it will transition to the first state in the ordering and write $\alpha_0$ on the tape, and if $\alpha_0$ to $\alpha_{k-1}$ is on the tape it will increment and transition to itself (like every other state), and if $\alpha_k$ is on the tape, $T_1$ halts.

So, the total effect is that by adding characters in our alphabet we can put a "side-algorithm" that lets us visit every state $K$ times, and we do this once $T_2$ halts. Since these are 'extra characters', we are assuming that these will never be written during our simulation of $T_2$, so we will never trigger this loop accidentally. Therefor, we visit every state $K$ times if and only if $T_2$ halts.