Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/425843506444509184
edited tags
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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.

Thanks in advance.

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.

Thanks in advance.

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.

Source Link
Ad Fundum
  • 229
  • 2
  • 6

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.

Thanks in advance.