# How to reduce EQU to UNI?

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

• yes, sry....i changed it :) – user596542 Jun 2 at 15:57
• Your description is unclear. What you need to do is to make an algorithm (or a TM) that takes input $u\# w$ and always halts with "yes" or "no". You need to describe when should this algorithm accept and when should it reject. You can assume that there is an algorithm/TM for UNI and you can use it in your algorithm for EQU. – frabala Jun 2 at 16:11
• yeah I know :D That algorithm i have so far looks something like this: Input u#v 1. Simulate u#v 2. accept The problem I see is, if u#v is not in EQU then our simulation (step 1.) may either never stop (which is fine) or it stops in some sort of an error state, which is a problem because 2. step is being executed, and this means we accept without u#v being in EQU. – user596542 Jun 2 at 16:18
• What does it mean to simulate $u\#w$? $u\#w$ is just the encoding of two machines. What do you simulate? – frabala Jun 2 at 16:21
• The simulation is about to decide whether u#v is in EQU or not. Edit: sry for writing the question so unclear...I tried my best – user596542 Jun 2 at 16:23

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.

• Nice! Thank you! :) – user596542 Jun 2 at 18:46