I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?

  • $\begingroup$ It has been a few years since my theory course but if I recall right, that is undecidable. Look into Rice's theorem, it may be useful for this. $\endgroup$
    – Hank Igoe
    Jan 9, 2021 at 10:37
  • 1
    $\begingroup$ I suggest you keep trying. $\endgroup$ Jan 9, 2021 at 10:45
  • $\begingroup$ @HankIgoe I did it differently as according to you you would by Rice's theorem? $\endgroup$
    – Paradojin
    Jan 9, 2021 at 21:47
  • $\begingroup$ @Paradojin Here is a demonstration of how it can be done with Rice's theorem, if you're interested: cs.stackexchange.com/questions/19876/… $\endgroup$ Jan 10, 2021 at 10:03

1 Answer 1


As you suggested, think how to reduce from the halting problem $Halt_{TM} = \{ \langle M, w\rangle: \text{$M$ halts on $w$} \}$. On input $\langle M, w\rangle$, the reduction should output a pair of TMs $\langle K_1, K_2\rangle$; such that $M$ halts on $w$ iff $L(K_1) = L(K_2)$.

This is somehow a basic reduction that can be done by standard tricks, so it would be a nice exercise to solve it alone. Here is a hint.

Hint: you can simplify things by fixing one of the machines $K_1$ or $K_2$ to be a constant machine that recognizes some fixed language. Then, think how to define the other machine depending on the reduction's input $\langle M, w\rangle$.

  • $\begingroup$ thanks this helped me a lot! $\endgroup$
    – Paradojin
    Jan 9, 2021 at 17:19
  • $\begingroup$ You're welcome. I'm glad it did help. $\endgroup$ Jan 9, 2021 at 17:20

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.