4
$\begingroup$

Let us define two languages of Turing machines. $$ EQ_{TM} = \{<M_1,M_2> : L(M_1) = L(M_2)\} $$ $$ ALL_{TM} = \{<M> : L(M) = \Sigma^*\} $$ It is easy to show that neither of the languages are in $RE \cup coRE$, and also it is easy to construct a reduction $ALL_{TM} \leq EQ_{TM}$.

I suspect that there is no reduction in the other direction, but I don't know how to prove it. Is there some sort of hierarchy of undecidable/non-recognizable languages that proves it?

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ IMO a direct proof is easier, but check out arithmetic hierarchy. To use the strictness of the arithmetic hierarchy, you need to show that EQ is hard for the larger one. Btw, this is not research-level, it looks like an exercise from a computability theory textbook and would be more appropriate on Mathematics or Computer Science. $\endgroup$ – Kaveh Jun 27 '13 at 9:04
  • $\begingroup$ Thanks Kaveh. I apologize if it's an exercise from a textbook, I never read this book. $\endgroup$ – Igor Shinkar Jun 27 '13 at 9:16
5
$\begingroup$

Let's fix the following definition for $L(M)$: it's the set of strings $x$ such that $M$ halts on input $x$.

Given machines $M_1,M_2$, consider a machine $M$ which accepts two inputs $x$ and $t$ and runs the following algorithm:

  1. Run $M_1$ on input $x$ for $t$ steps.
  2. If $M_1$ halted: run $M_2$ on $x$.
  3. Otherwise:
    1. Run $M_2$ on input $x$ for $t$ steps.
    2. If $M_2$ halted: run $M_1$ on $x$.
    3. Otherwise: halt.

The machine $M$ rejects an input $x,t$ iff one of the machines $M_1,M_2$ accepts $x$ within $t$ steps and the other one rejects $x$. So $M$ accepts all inputs iff $L(M_1) = L(M_2)$.

| cite | improve this answer | |
$\endgroup$

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.