# Show that the equivalence problem for deterministic Turing machines and its complement is not semi-decidable

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.

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.

• 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. – CsStudent13 Jun 2 '13 at 16:22
• Added the reduction. – Shaull Jun 2 '13 at 19:24
• 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. – jmite Jun 2 '13 at 22:06
• @jmite - the OP needs to show a language that is not in RE nor in coRE. Rice's theorem won't suffice here. – Shaull Jun 3 '13 at 3:52
• It's not enough but it's a good start, especially for the "easy exercise" part he's talking about – jmite Jun 3 '13 at 4:24