# Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?

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?

• 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. Jan 9, 2021 at 10:37
• I suggest you keep trying. Jan 9, 2021 at 10:45
• @HankIgoe I did it differently as according to you you would by Rice's theorem? Jan 9, 2021 at 21:47
• @Paradojin Here is a demonstration of how it can be done with Rice's theorem, if you're interested: cs.stackexchange.com/questions/19876/… Jan 10, 2021 at 10:03

## 1 Answer

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

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