# Is it possible to prove EQTM is undecidable by the Rice theorem?

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.

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.
• 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. – Ad Fundum Jan 21 '14 at 19:47