0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
7
  • $\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
  • $\begingroup$ Added the reduction. $\endgroup$
    – Shaull
    Jun 2, 2013 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$ Jun 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$
    – Shaull
    Jun 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$ Jun 3, 2013 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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