1

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 "...


Only top voted, non community-wiki answers of a minimum length are eligible