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

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?

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.

• Did you make sure that it visits $q_0$ or $q'_0$ twice?
– Joni
Aug 1 '12 at 13:45
• @Joni: The new start state $q^'_0$ should be visited twice (accepting run) or once (rejecting or cycling). Aug 1 '12 at 14:02
• but shouldn't I make sure that $q_o$ itself will be visited twice? the question is that a specific given state is visited twice, not that there's one that visited twice,any one, or that you can give the one that would be visited twice. maybe I misunderstood you. the reduction is $<M,x>=M'$.
– Joni
Aug 1 '12 at 14:14
• @Joni: In my understanding the start state has to be visited twice, this state is usually denoted by $q_0$. However, I denoted it for the machine $M'$ as $q^'_0$. You can rename all states if you want. Aug 1 '12 at 14:28
• I didn't mean the start state, sorry for misleading.
– Joni
Aug 1 '12 at 14:33