Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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?).
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.
