Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

Question

I'm trying to prove that

$L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$.

I'm not sure whether to reduce the halting problem to it or not. I tried to construct a new machine $M'$ for $(\langle M \rangle,w)$, such that $M'$ visits $q_0$ twice, iff $M$ halts on $w$. This is specific $q_0$ given to me, but I didn't come to any smart construction, which would yield the requested. Maybe it's easier to show that it's $RE$ and not $coRE$? It is obvious that it's in $RE$, and I need to show that $L_2^{c}$ is not in $RE$.

What should I do?

Answer 1

Don't make this more complicated than it is. Instead of giving you a full solutions, I will give you a partial solution, which should allow you to work out the details by yourself:

Every TM be turned into a TM that visits its initial state exactly once. To do so, introduce a new state $q^'_0$, which will be the new start state. Then add a $\varepsilon$-transition from $q^'_0$ to $q_0$. This is the only way to "leave" the state $q'_0$.

For this modified machine, a accepting run visits the initial state once, and ends in the accepting state. What is left to do is to modify the machine further, such that it jumps back to $q^'_0$, after the machine was in the accepting state. But you have to assure that when $q^'_0$ is visited the second time, you will jump to a new accepting state. But it's not difficult to record how often you visited a state.

If you want that another state is visited twice, then you can always made a detour in the beginning that visits this state (you record that the machine is in "detour" mode be writing a flag on a special tape). Than you reroute the normal computation, such that if it should visit the requested state it visits a copy of this state. Finally, when accepting, you jump back to the requested state. Conceptually, this is not very different to relabeling the states.