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.

| cite | improve this answer | |
  • $\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$ – CsStudent13 Jun 2 '13 at 16:22
  • $\begingroup$ Added the reduction. $\endgroup$ – Shaull Jun 2 '13 at 19:24
  • 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$ – jmite Jun 2 '13 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$ – Shaull Jun 3 '13 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$ – jmite Jun 3 '13 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.