# checking whether turing machine passes at least k>2 states before accepting a word

$$L=\{\langle M,k\rangle \mid\exists w\in L(M) \text{ such that M passes at least k>2 distinct states before accepting w}\}$$

I try to think of reduction to prove that this language is neither RE nor coRE. How to approach this problem? Is there a hint, or intuition?

I usually check whether Rice can be used, but the question here is not about the language itself

Clearly $$L$$ is acceptable (just simulate $$M$$ and keep track of the number of distinct states encountered during the simulation). We now show that it is not decidable.
If $$L$$ were decidable, you would be able to solve the Halting problem as follows: given a TM $$T$$ and an input $$x \in \Sigma^*$$, construct a TM $$M$$ that ignores its input, simulates $$T$$ with input $$x$$ and, when the simulation is complete, accepts. You can further ensure that, if $$M$$ accepts, then it also traverses at least $$3$$ distinct states by just transitioning from the initial state to another (distinct) state before starting the simulation of $$T$$.
Now check whether $$\langle M, 3 \rangle \in L$$. If the answer is affirmative, then there is some $$w \in \Sigma^*$$ for which $$M(w)$$ accepts, showing that $$T(x)$$ halts. If the answer is negative then $$M$$ never halts, showing that $$T(x)$$ does not halt.
• Just build $M$ so that it goes form its initial state to another state, and then simulates $T$. This is already ensures that $M$ traverses at least $2$ distinct states. When (if) the simulation of $T$ completes, $M$ will move to the accepting state. Therefore if $T$ halts, $M$ visits at least $3$ distinct states. – Steven Jun 23 at 16:10