# 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.

## 1 Answer

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. Jun 2, 2013 at 16:22
• Added the reduction. Jun 2, 2013 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. Jun 2, 2013 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. Jun 3, 2013 at 3:52
• It's not enough but it's a good start, especially for the "easy exercise" part he's talking about Jun 3, 2013 at 4:24