# EQtm is not mapping reducible to its complement

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?

• Where exactly did you get stuck? What are your thoughts? Jan 29 '16 at 17:12
• 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. Jan 29 '16 at 17:16
• 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 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?).

• Can you clarify what Pi_2 - complete means as well as what TOT refers to and what Sigma_2 complete means? Feb 6 '16 at 15:06
• 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. Feb 6 '16 at 16:34
• I see, and so the inequality is NP complete and checking equality is co-NP complete and we can't reduce between the two? Feb 6 '16 at 16:37
• 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. Feb 6 '16 at 16:45
• Which one is NP-hard and which one is CoNP-hard? Feb 6 '16 at 16:52

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:

1. Obtain own description $$\langle F \rangle$$ via the recursion theorem (Sipser 6.3)
2. Write out the description $$\langle A_0 \rangle$$ of the following TM. On input $$\langle M,w \rangle$$:
• Save the constant string $$\langle F \rangle$$
• Save $$\langle M \rangle$$
• Simulate step (4) and (5) of $$\langle F \rangle$$ to get $$\langle B \rangle$$
• Compute $$\langle M', X' \rangle = t(\langle M, B \rangle)$$
• Simulate $$\langle M' \rangle$$ on $$w$$.
3. Use the recursion theorem to construct $$A$$ which computes $$A_0(\langle A, w \rangle)$$ on input $$w$$.
4. Write out the description $$\langle B_0 \rangle$$ of the following TM. On input $$\langle M,w \rangle$$:
• Save the constant string $$\langle F \rangle$$
• Save $$\langle M \rangle$$
• Simulate step (2) and (3) of $$\langle F \rangle$$ to get $$\langle A \rangle B$$
• Compute $$\langle X', M' \rangle = t(\langle A, M \rangle)$$.
• Simulate $$\langle M' \rangle$$ on $$w$$.
5. Use the recursion theorem to construct $$B$$ which computes $$B_0(\langle B, w \rangle)$$ on input $$w$$
6. print $$\langle A, B \rangle$$.

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.

• I think this proof is incorrect. In the equation $\langle f_1^F(G), f_2^G(F) \rangle = \langle F^\prime, G^\prime \rangle$, the fixed-point theorem only handles unary functions and thus does not guarantee existence of $F^\prime$ and $G^\prime$ with the same languages as their counterparts on the left-hand side. The fixed points $F$ and $G$ are defined here in terms of each other (in particular, we have $M = G$ when finding the fixed point of $f_1^M$, but $M = F$ for $f_2^M$) and thus there is a circular definition that cannot be computable. Oct 20 '20 at 16:46
• Lambda notation makes this easier to express. To make this more readable, I do not use the angular brackets for pairs. Define the curried version of the reduction f by $$f_C = \lambda X. \lambda Y. f(X,Y)$$ Then we let $f^1 = f_C(F)$ and $f^2 = f_C(G)$. $f^1$ has a fixed point, $F’$. $f^2$ has a fixed point, $G’$. This follows from Rogers’ fixed point theorem and the assumption that f is total and recursive. Clearly, $f(F,G) = (f^1(G),f^2(G))$. But now $f(F’,G’) = (F’,G’)$. And then we have, by the faithfulness assumption for $f$ that $L(F’) = F(G’)$ iff $L(F’) \neq L(G’)$. Oct 20 '20 at 18:49
• Some of the results in your comment don't make sense. If you we take the definition of $f^1$ and $f^2$, we have $f^1 = \lambda Y . f(F, Y)$, and thus $f^1(G) = f(F, G)$. Similarly, $f^2(G) = f(G, G)$. Then it is not true that $f(F, G) = (f^1(G), f^2(G))$. The comment doesn't address my main point that you cannot compute the fixed points here, because they depend on each other: in your answer $f_1^M(F) = F^\prime$, this entire equation is parameterized by $M$. You cannot use the fixed point theorem to compute both $F$ and $G$, since each computation depends on the result of the other. Oct 20 '20 at 19:30
• In other words, this answer says that $G$ is the fixed point of $f_1^F$ while $F$ is the fixed point of $f_2^G$. This definition clearly has a cycle, and thus cannot be computed using the fixed point theorem. Oct 20 '20 at 19:48
• Note that it may be tempting to argue something like this: "let $N$ be the fixed point of $f_1^M$ and let $Q$ be the fixed point of $f_2^N$. This is a computable function $g$ taking $M$ to $Q$ and thus has a fixed point $F$." However the problem with this argument is that $g$ may not necessarily take $F$ to itself; it only needs to take $F$ to a possibly different machine with the same language. Hence, this construction cannot be used to resolve the circular definition. Oct 21 '20 at 3:34

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}}$$.