I would like to show that $$EQ_{DTM} = \{ (\langle M_1\rangle,\langle M_2\rangle) \mid M_1\text{ and } M_2 \text{ are DTMs and } L(M_1)=L(M_2)\}$$ and $$\overline{EQ_{DTM}}$$ are not semi-decidable. I think there must be a reduction from the complement of the halting problem.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
I think an easier way to approach this is by reducing from $$ALL_{TM}=\{\langle M \rangle: M \text{ is a DTM and } L(M)=\Sigma^*\}$$
Showing that $ALL_{TM}$ is not in in RE nor coRE a standard exercise, and you can find the solution e.g. here
Then, we can reduce from $ALL_{TM}$ to $EQ_{TM}$ as follows: given input $\langle{M\rangle}$ for $ALL_{TM}$, we output $\langle{M,T\rangle}$ where $T$ is a fixed TM that accepts every input immediately. Thus, $L(T)=\Sigma^*$, and we have that $L(M)=L(T)$ iff $L(M)=\Sigma^*$, so the reduction is correct.
-
$\begingroup$ Thank you very much. The first point is clear to me, but the second (the "easy exercise") is not. I'm not very familiar with reducing and need some help. $\endgroup$ Jun 2, 2013 at 16:22
-
-
1$\begingroup$ Looking up Rice's theorem would probably be a good start if you're not familiar with reductions. Basically any question about the language accepted by a Turing machine is undecidable. $\endgroup$– jmiteJun 2, 2013 at 22:06
-
$\begingroup$ @jmite - the OP needs to show a language that is not in RE nor in coRE. Rice's theorem won't suffice here. $\endgroup$– ShaullJun 3, 2013 at 3:52
-
1$\begingroup$ It's not enough but it's a good start, especially for the "easy exercise" part he's talking about $\endgroup$– jmiteJun 3, 2013 at 4:24