0
$\begingroup$

$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

Improve this question
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ How can I ensure that M visits at least three states before accepting? It doesn't depend on T? Or do I have to build M so that I add 3 states, first going through them without changing anything, and then running T? $\endgroup$ – Ella Jun 23 '20 at 10:55
  • $\begingroup$ 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. $\endgroup$ – Steven Jun 23 '20 at 16:10
  • $\begingroup$ got it. thank you very much! $\endgroup$ – Ella Jun 24 '20 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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