Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
$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.
