# Is $\{\langle \langle M\rangle, q\rangle\mid M(\varepsilon)$ enters state $q$ infinite times$\}$ not in RE?

I'm trying to use reduction $$\overline{HP} \leq L$$, but I just can't think of a way to do so.
Any help would be appreciated!

• "Is that a TM not in RE?" makes absolutely no sense.
– Arno
Feb 21 at 11:49
• I could have guessed, but using confused language just makes it much harder for you to actually figure stuff out.
– Arno
Feb 21 at 12:06

Hint: given a Turing machine $$M$$ and a word $$w$$ over $$M$$'s alphabet, consider a machine $$T$$, that on the empty word simulates the run of $$M$$ on $$w$$. Can you force $$T$$ to visit a state infinitly often if the simulation does not halt? Note that ofcourse there is such a state but we do not know it in advacnce to output it in the reduction, but there is a simple way around this: you can modify the simulation anyway you see fit.
Using reduction $$\overline{HP} \leq L$$ with $$f\left ( \left ( \left \langle M \right \rangle ,x \right ) \right ) = \left ( \left \langle M_x \right \rangle ,q\right )$$ where $$M_x$$ is a TM which simulates M on input x, but between every two steps, it goes into state q. If $$M_x$$ halts, reject.
This means that if $$\left ( \left \langle M \right \rangle ,x \right ) \in \overline{HP}$$ then M does not halt on x, which means $$M$$ will be in an infinite loop which means $$M_x$$ will visit state q infinite times.
If $$\left ( \left \langle M \right \rangle ,x \right ) \notin \overline{HP}$$ then $$M$$ will halt which means $$M_x$$ visits q $$n \in \mathbb{N}$$ times.
• Correct, but I encourage you to write it more clearly. (1) $M_x$, on input $y$, ignores $y$ and then simulates the run of $M$ on $x$. (2) Some people use "loop" to indicate a state visited infinitely often, but the use of "loop" usually means a loop of configurations. If you meant a loop of states, you should write that explicitly: "a loop of states". (3) "it goes into a state $q$, where $q$ a is special state of $M_x$". Feb 21 at 14:53