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?).

| cite | improve this answer | |
  • $\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

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.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – xdavidliu Oct 20 at 16:46
  • $\begingroup$ 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’)$. $\endgroup$ – Hans Hüttel Oct 20 at 18:49
  • $\begingroup$ 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. $\endgroup$ – xdavidliu Oct 20 at 19:30
  • $\begingroup$ 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. $\endgroup$ – xdavidliu Oct 20 at 19:48
  • $\begingroup$ 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. $\endgroup$ – xdavidliu Oct 21 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}}$.

| cite | improve this answer | |

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.