patternMinor
Is it possible to prove EQTM is undecidable by the Rice theorem?
Viewed 0 times
theundecidableeqtmpossibleprovetheoremrice
Problem
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.
I have proven this problem by reduction to $E_{TM}$, but was wondering if it was easier to do with Rice.
Solution
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.
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.
Context
StackExchange Computer Science Q#19876, answer score: 6
Revisions (0)
No revisions yet.