6
$\begingroup$

Given the problem $EQ_{TM} = \{ \langle M_1, M_2\rangle \mid M_1 \text{ and } M_2 \text{ are } TM, L_{M_1} = L_{M_2}\}$, is it possible to prove that this is undecidable by using (a variant of) Rice theorem?

I have proven this problem by reduction to $E_{TM}$, but was wondering if it was easier to do with Rice.

$\endgroup$
6
$\begingroup$

You can reduce it to a problem about single Turing machines by fixing one of the inputs. For example, you can take $M_2$ to be some Turing machine which accepts nothing. This shows that $EQ_{TM}$ is at least as hard as deciding emptiness.

Another approach is to encapsulate the pair of Turing machines $M_1,M_2$ in one Turing machine $M$, which upon input $0x$ will simulate $M_1$ on $x$, and upon input $1x$ will simulate $M_2$ on $x$ (on the empty input it can arbitrarily halt). There is a simple reduction showing that $EQ_{TM}$ is equivalent to the corresponding problem for $M$, and then you can apply Rice's theorem.

$\endgroup$
  • $\begingroup$ Yea, that's what I meant by reducing to $E_{TM}$ :) What I want to know is if it is also provable by using Rice's Theorem. $\endgroup$ – Ad Fundum Jan 21 '14 at 19:47
  • $\begingroup$ You can come up with several generalizations of Rice's theorem that will apply. One of them will encapsulate the proof in this answer. Others will be more general. If you understand the proof of Rice's theorem, you should be able to conjecture and proof such generalizations. $\endgroup$ – Yuval Filmus Jan 21 '14 at 20:56
  • $\begingroup$ See my updated answer for another example. $\endgroup$ – Yuval Filmus Jan 21 '14 at 20:57

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.