This is a problem from Sipser's book (marked with an asterisk).

$EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$

We know that neither $EQ_{TM}$ nor $\overline{EQ_{TM}}$ are recognizable so unsure how to go about proving there can't be a mapping reduction from one to the other.

Any hints?

  • 3
    $\begingroup$ Where exactly did you get stuck? What are your thoughts? $\endgroup$ – vonbrand Jan 29 '16 at 17:12
  • $\begingroup$ First I realized that it's not useful to use the reduction from any other language to either $EQ_{TM}$ or $\overline{EQ_{TM}}$ and then look for contradiction (the language would then be recognizable or decidable) - because we know they are not recognizable. $\endgroup$ – user1255841 Jan 29 '16 at 17:16
  • $\begingroup$ Then I tried to use the fact that I have a 1-to-1 map from $<M_1, M_2>$ to $<N_1,N_2>$ where $L(M_1) = L(M_2)$ and $L(N_1) \ne L(N_2)$ . Now I am trying to find a language that I can construct a TM to recognize using this map - and so far not finding any $\endgroup$ – user1255841 Jan 29 '16 at 17:19

Your language is $\Pi_2$-complete: it can be written as a $\Pi_2$ formula, and TOT can be reduced to it. The complement is therefore $\Sigma_2$-complete. No computable reductions can exist between $\Pi_2$-complete and $\Sigma_2$-complete sets (why?).

  • $\begingroup$ Can you clarify what Pi_2 - complete means as well as what TOT refers to and what Sigma_2 complete means? $\endgroup$ – NateSHolland Feb 6 '16 at 15:06
  • $\begingroup$ These are levels of the polynomial hierarchy, explained for example on Wikipedia. TOT is the language of all Turing machines that halt on all inputs. $\endgroup$ – Yuval Filmus Feb 6 '16 at 16:34
  • $\begingroup$ I see, and so the inequality is NP complete and checking equality is co-NP complete and we can't reduce between the two? $\endgroup$ – NateSHolland Feb 6 '16 at 16:37
  • $\begingroup$ It's not known to be in NP. In fact, it's conjectured to be in neither NP nor coNP. It's both NP-hard and coNP-hard, though. $\endgroup$ – Yuval Filmus Feb 6 '16 at 16:45
  • $\begingroup$ Which one is NP-hard and which one is CoNP-hard? $\endgroup$ – NateSHolland Feb 6 '16 at 16:52

If there were a reduction $f$ from $EQ_\mathsf{TM}$ to $\overline{EQ_\mathsf{TM}}$, then it would be a computable function satisfying that

$$f(\langle M_1,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

where $L(M_1) = L(M_2) \iff L(M'_1) \neq L(M'_2)$.

We would then also have computable functions $f_1, f_2 : \Sigma^* \rightarrow \Sigma$ defined by

$$f_1((\langle M_1 \rangle, \langle M_2 \rangle)) = \langle M'_1 \rangle \text{ if } f(\langle M_1,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

$$f_2(\langle M_1 \rangle, \langle M_2 \rangle)) = \langle M'_2 \rangle \text{ if } f(\langle M_1,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

But then by the first recursion theorem, we would have "curried" versions of these for any given $M$:

$$f^M_1(\langle M_2 \rangle) = \langle M'_1 \rangle \text{ if } f(\langle M,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

$$f^M_2(\langle M_1 \rangle) = \langle M'_2 \rangle \text{ if } f(\langle M_1,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

By the fixed-point theorem, there must then be a machine $F$ such that

$$f^M_1(\langle F \rangle) = \langle F' \rangle$$

where $L(F') = L(F)$ and a machine $G$ such that

$$f^M_2(\langle G \rangle) = \langle G' \rangle$$

and $L(G') = L(G)$.

But then we get that $f(\langle F, G \rangle) = \langle f^F_1(\langle G \rangle), f^G_2(\langle F \rangle) \rangle = (\langle F', G' \rangle)$. Clearly we do not have that $L(F) = L(G) \iff L(F') \neq L(G')$.

We have thus reached a contradiction, using only the assumption that $f$ existed.


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.