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?).
Suppose a computable mapping reduction $t: \Sigma^* \to \Sigma^*$ from $EQ_{TM}$ to $\overline{EQ_{TM}}$ exists.
We want to create TM's $A,B$ such that for $\langle A', B' \rangle = t(\langle A,B \rangle)$, we have \begin{align} L(A) &= L(A') \\ L(B) &= L(B') \end{align}
We will nest the recursion theorem to accomplish this goal. Our "inner" use of the recursion theorem will be explicit.
Let $F$ be the following TM, which ignores its input:
Note that when running the TM $A_0$ (and analogously for $B_0$), the simulation of $\langle F \rangle$ is purely "code-manipulation" of the program $\langle B_0 \rangle$: both writing out the description and constructing the recursive variant do not involve running $B_0$ at all. The latter is apparent from a close reading of the definition of $\langle R \rangle$ in Sipser, page 249. This ensures the definitions of $A$ and $B$ are not circular.
Running $F$ generates $\langle A,B \rangle$. Let $\langle A', B' \rangle = t(\langle A,B \rangle)$. Since $A$ simulates $A'$ and $B$ simulates $B'$, we have that $L(A) = L(A')$ and $L(B) = L(B')$.
It must be the case that $L(A) = L(B)$ or $L(A) \neq L(B)$. In the first case, we have \begin{align*} L(A) = L(B) = L(B') \neq L(A') = L(A) \end{align*} In the second case, \begin{align*} L(A) \neq L(B) = L(B') = L(A') = L(A) \end{align*} In either case we have elicited a contradiction of the assumption that the mapping $t$ exists.
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.
Suppose $EQ_\mathrm{TM} \leq_\mathrm{m} \overline{EQ_\mathrm{TM}}$. Then there exists an $f : \Sigma^\star \rightarrow \Sigma^\star$ such that $f(w) \in EQ_\mathrm{TM}$ if and only if $w \in \overline{EQ_\mathrm{TM}}$.
Without loss of generality, we can assume $f(w)$ is always a pair $\langle M_1, M_2 \rangle$ of TMs, as opposed to gibberish in the case that $w \in EQ_\mathrm{TM}$. To ensure this, wrap $f$ with a simple procedure that converts any $f(w)$ that is not a pair of TMs to some (doesn't matter which) pair of non-equivalent TMs.
Now for any TMs $A$ and $B$, we have $f(A, B) = \langle A^\prime, B^\prime \rangle$, where $L(A^\prime) \neq L(B^\prime)$ if and only if $L(A) = L(B)$.
Now define the function $a(B)$ as the $A$ that, given $B$, will result in $L(A^\prime) = L(A) = L(a(B))$ above. This function $a(B)$ is computable using the fixed point version of the recursion theorem (6.8 in Sipser) with input $A$ and output $A^\prime$.
Now let $p(B)$ be the $B^\prime$ that results from $f(a(B), B)$. Let $P$ be the fixed point of $p$, i.e. $L(P) = L(p(P))$. We then have $f(a(P), P) = \langle A^\prime, p(P)\rangle$. By construction, we still have $L(a(P)) = L(A^\prime)$.
Can we have $L(a(P)) = L(P)$? No, because if so, then from the preceding equalities, we would also have $L(a(P)) = L(A^\prime) = L(p(P))$, and thus $f$ would be taking an element of $EQ_\mathrm{TM}$ to another element of $EQ_\mathrm{TM}$, which it is forbidden from doing by definition. Similarly, we cannot have $L(a(P)) \neq L(P)$, since that would result in $L(a(P)) = L(A^\prime) \neq L(p(P))$ and thus $f$ would be taking an element of $\overline{EQ_\mathrm{TM}}$ to another element $\overline{EQ_\mathrm{TM}}$, which it is forbidden from doing.
Since we have ruled out all possibilities, we see that $EQ_\mathrm{TM} \nleq_\mathrm{m} \overline{EQ_\mathrm{TM}}$.
