# Proof of undecideability that one state is reached before another

I'm trying to show that, for a deterministic Turing machine $$M=(Q,\Gamma,\Sigma,\delta,q_0)$$, the language $$K$$, which includes all of the words $$w \in \Sigma^\ast$$ where the calculation of $$M$$ on $$w$$ pass on the state $$q$$ before reaching $$q'$$, but if $$q'$$ is never reached then $$w$$ is not in $$K$$, is both recursively enumerable and undecidable.

I am thinking that this could be solved by a reduction of the Halting problem, but I do not know how to proceed.

Reducing the Halting problem to this problem would mean that a machine $$M$$ with data $$w$$ will halt on $$w$$ iff a machine $$M'$$ with data $$w$$ that first passes state $$q$$ then $$q'$$. I see that if we were to associate $$q$$ in $$M'$$ with $$q_0$$ in $$M$$ and $$q'$$ in $$M'$$ with $$q_f$$ in $$M$$ we could associate part of the problem with the halting problem, but how can the condition "$$q_f$$ must not be reached first" be included?

• Start by stating what it means from the halting problem to reduce to your problem. Often people get stuck since they skip this step. – Yuval Filmus Feb 18 '19 at 4:10

Let us follow the hint given by Yuval.

What is the halting problem?

It is the problem of accepting the following language.

$$\text{HALT}= \{⟨M, w⟩ : M \text{ is a TM and }M\text{ will halt on input } w\}$$

What is the current problem?

It is the problem of accepting the following language.

\begin{align} \text{One}&\text{StateBeforeAnother} = \{⟨M, q, q',w⟩: M\text{ is a TM} \\&\wedge q\text{ and } q'\text{ are two states of }M \\ &\wedge \left(M \text{ will reach } q' \text{ on input } w\right.\\ &\vee M \left.\text{ will reach } q \text{ before reaching } q' \text{ on input } w \right)\} \end{align}

How to define $$\text{HALT}$$ in a way similar to how $$\text{OneStateBeforeAnother}$$ is defined?

The idea is that if we can formulate $$\text{HALT}$$ in a way similar to the way $$\text{OneStateBeforeAnother}$$ is defined, then we might reduce the former to the latter.

$$M$$ halts on input $$w$$ means $$M$$ reaches a halt state on input $$w$$. $$\text{OneStateBeforeAnother}$$ is about $$M$$ reaches $$q$$ and then $$q'$$.

Let us try brute pattern matching.

• Let $$q$$ be a halt state. $$M$$ reaches $$q$$, the halt state and then reaches $$q'$$. That cannot happen since the halt state is the last state. Sigh!

• Let $$q'$$ be a halt state. $$M$$ reaches $$q$$ and then reaches $$q'$$, the halt state. That makes sense. What is $$q$$ then? How about letting $$q$$ be the initial state of $$M$$?

Great, we have just found the following reduction, where $$q_0$$ is the initial state of $$M$$ and $$q'$$ is the halt state of $$M$$ on input $$w$$.

$$⟨M, w⟩\in\text{HALT} \to ⟨M, q_0, q',w⟩\in\text{OneStateBeforeAnother}$$

Wait, this is not a well-defined reduction as $$q'$$ cannot be known at the time of reduction since it depends on how $$M$$ runs on input $$w$$, the undecidable halting problem!

I will leave you to conquer the problem above, how to require $$q'$$ to be a halt state without dependence to $$M$$ and $$w$$.

• Isn't there a problem with defining q to be q$_0$? Is there a guarantee that M reaches q? – QuantumDM Feb 18 '19 at 13:28
• Given (the string that encodes) $M$, we can find $q_0$ in constant (or at most linear) time. If $q$ is the initial state, it has been always when $M$ begins to run since it is the initial state. – John L. Feb 18 '19 at 13:31
• If it is too difficult to overcome the last obstacle, please check a further hint in the last paragraph of this answer. – John L. Feb 18 '19 at 17:02
• Thank you, this was very helpful! – QuantumDM Feb 18 '19 at 17:20