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 at 10:37
  • 1
    $\begingroup$ I suggest you keep trying. $\endgroup$ – Yuval Filmus Jan 9 at 10:45
  • $\begingroup$ @HankIgoe I did it differently as according to you you would by Rice's theorem? $\endgroup$ – Paradojin Jan 9 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$ – Bader Abu Radi Jan 10 at 10:03

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 at 17:19
  • $\begingroup$ You're welcome. I'm glad it did help. $\endgroup$ – Bader Abu Radi Jan 9 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.