2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ yes, sry....i changed it :) $\endgroup$ – user596542 Jun 2 at 15:57
  • $\begingroup$ 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. $\endgroup$ – frabala Jun 2 at 16:11
  • $\begingroup$ 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. $\endgroup$ – user596542 Jun 2 at 16:18
  • $\begingroup$ What does it mean to simulate $u\#w$? $u\#w$ is just the encoding of two machines. What do you simulate? $\endgroup$ – frabala Jun 2 at 16:21
  • $\begingroup$ 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 $\endgroup$ – user596542 Jun 2 at 16:23
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice! Thank you! :) $\endgroup$ – user596542 Jun 2 at 18:46

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.