So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this:

$M_1$ and $M_2$ behave the same way on an input $x$, when they both don't halt, or when they both accept $x$ or when they both halt and reject $x$.

I found a reduction from the halting problem which uses the fact that if the Turing machines behave in the same way, than they must have the same language. But this all breaks down in the case that $M_1$ rejects $x$ and $M_2$ doesn't halt, obviously they could have the same language, but they don't act in the same way.

I do think the best way to approach this is by reducing from the halting problem, but I just can't find a valid reduction. Any help would be appreciated.


1 Answer 1


You were very close to the answer. The special case you mentioned can be handled by hand. Modify the machines resulting from the reduction such that, for each transition, where the machine halts and rejects, let the resulting machine go into an endless loop instead.

Now each machine either accepts or goes into an endless loop. That means, checking if both machines are equivalent on an input $x$ is checking whether both accept the input $x$.

  • 1
    $\begingroup$ "each time the machine halts and rejects" We don't have this information. The halting problem: $H = \left\{ \left \langle M \rangle, x \: \right| x \in L(M) \right\} $. Either $M$ accepts $x$ or it doesn't. If $x \notin L(M)$, $M$ either doesn't halt or it halts and rejects, but we can't tell which. $\endgroup$
    – Karla
    Jan 5, 2020 at 20:44
  • $\begingroup$ I probably did not formulate the idea correctly, I meant to look into the transitions function, and instead of transition to the state "no", go into an endless loop. I updated the answer correspondingly $\endgroup$ Jan 5, 2020 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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