How to reduce EQU to UNI?

Question

Let $$\texttt{EQU}=\{u\#v \mid T(M_u)=T(M_v)\} \\ \texttt{UNI}=\{w \mid T(M_w)= \Sigma^*\}$$

How can you prove $\texttt{EQU} \leq \texttt{UNI}$?

The idea I have so far is, to simulate the TM that decides whether a given $w = u\#v$ is in $\texttt{EQU}$ or not. In case it is, our TM halts and we simply accept everything ($f(w) \in \texttt{UNI}$). But, as far as I know, there are two options for $w \notin \texttt{EQU}$ :

1. The simulation won't ever stop
2. The simulation stops but not with $q \in F$

The first case isn't a problem as I think. We won't ever accept because the TM never finishes with simulating. But the second case is a problem, as the TM accepts with $w \notin \texttt{EQU}$.

Answer 1

This answer assumes that $T(M)$ is the set of inputs on which $M$ halts.

Given an instance $u\#v$ of $\texttt{EQU}$, we construct a new Turing machine $w$ with the following input:

• A string $x$.
• An integer $t$.

The machine acts as follows.

1. Run $u$ on $x$ for $t$ steps. If $u$ halted, then run $v$ on $x$.

2. Run $v$ on $x$ for $t$ steps. If $v$ halted, then run $u$ on $x$.

3. Halt.

I claim that $w \in \texttt{UNI}$ iff $u\#v \in \texttt{EQU}$. To see this, consider some input $x$. We distinguish four different cases:

1. Both $u$ and $v$ halt on $x$. In this case $w$ will halt on $x,t$ for all $t$ (since "run $v$ on $x$" and "run $u$ on $x$" will always terminate).
2. Both $u$ and $v$ don't halt on $x$. In this case the test in steps 1–2 will always fail, and so $w$ will always reach step 3 and halt on $x,t$, for any $t$.
3. $u$ halts on $x$ after $t$ steps, and $v$ doesn't halt on $x$. In this case $w$ won't halt on $x,t$, getting stuck at step 1.
4. $v$ halts on $x$ after $t$ steps, and $u$ doesn't halt on $x$. In this case $w$ won't halt on $x,t$, getting stuck at step 2.

---

How did I construct this machine? First of all, let us note that $\texttt{UNI}$ is $\Pi_2$-complete. This means that we can reduce to it any language $L$ such that $$ x \in L \leftrightarrow \forall y \exists z \, \Pi(x,y,z), $$ where $\Pi$ is any computable predicate. Next, using $H(u,x,t)$ for "$M_u$ halts on $x$ within $t$ steps", we see that $$ u\#v \in \texttt{EQU} \leftrightarrow \forall x (\exists s \, H(u,x,s) \land H(v,x,s)) \lor (\forall t \, \lnot H(u,x,t) \land \lnot H(v,x,t)). $$ Rearranging, this is the same as $$ u\#v \in \texttt{EQU} \leftrightarrow \forall x \forall t \exists s \, (H(u,x,s) \land H(v,x,s)) \lor (\lnot H(u,x,t) \land \lnot H(v,x,t)). $$ Therefore $\texttt{EQU}$ should reduce to $\texttt{UNI}$. Taking a look at the $\Pi_2$-completeness proof, we reach the machine outlined above.

---

It is easy to see that $\texttt{UNI}$ reduces to $\texttt{EQU}$, by mapping $w$ to $w\#h$, where $M_h$ is a machine that always halts. We conclude that $\texttt{UNI}$ is also $\Pi_2$-complete.