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?


1 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.

  • $\begingroup$ Did you make sure that it visits $q_0$ or $q'_0$ twice? $\endgroup$
    – Joni
    Aug 1, 2012 at 13:45
  • $\begingroup$ @Joni: The new start state $q^'_0$ should be visited twice (accepting run) or once (rejecting or cycling). $\endgroup$
    – A.Schulz
    Aug 1, 2012 at 14:02
  • $\begingroup$ 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'$. $\endgroup$
    – Joni
    Aug 1, 2012 at 14:14
  • 1
    $\begingroup$ @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. $\endgroup$
    – A.Schulz
    Aug 1, 2012 at 14:28
  • $\begingroup$ I didn't mean the start state, sorry for misleading. $\endgroup$
    – Joni
    Aug 1, 2012 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.