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$
$\endgroup$
4
-
$\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 IgoeCommented Jan 9, 2021 at 10:37
-
1$\begingroup$ I suggest you keep trying. $\endgroup$– Yuval FilmusCommented Jan 9, 2021 at 10:45
-
$\begingroup$ @HankIgoe I did it differently as according to you you would by Rice's theorem? $\endgroup$– ParadojinCommented 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$– Bader Abu RadiCommented Jan 10, 2021 at 10:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
answered Jan 9, 2021 at 10:57
-
-
$\begingroup$ You're welcome. I'm glad it did help. $\endgroup$ Commented Jan 9, 2021 at 17:20