1
$\begingroup$

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?

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

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$.

$\endgroup$
  • $\begingroup$ Isn't there a problem with defining q to be q$_0$? Is there a guarantee that M reaches q? $\endgroup$ – QuantumDM Feb 18 at 13:28
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Feb 18 at 13:31
  • $\begingroup$ If it is too difficult to overcome the last obstacle, please check a further hint in the last paragraph of this answer. $\endgroup$ – Apass.Jack Feb 18 at 17:02
  • $\begingroup$ Thank you, this was very helpful! $\endgroup$ – QuantumDM Feb 18 at 17:20

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.