Given $A, B$ languages over $\Sigma,$ Prove/Disprove: If $A _{\leq M} B$ and $B _{\leq M} A$ then $A=B$.

I would like to disprove this claim, with the languages $H_{TM}$ and $H_\epsilon = \{\langle M \rangle\ |\ M \ halts\ on\ empty\ tape\}$

I can prove $H_{TM} {_{\leq M}} H_\epsilon$ by taking $\langle M,w \rangle$, and build new machine $M’_w$ that writes $w$ on tape and then simulates $M$. Then $\langle M,w \rangle \in H_{TM} \iff \langle M'_w \rangle ∈ H_\epsilon$

I got stuck proving the other direction.

Any help is appreciated.


1 Answer 1


Let $\Sigma = \{0,1\}$, $A=\{0\}$, $B=\{1\}$.

Define the following reductions:

$f(0)=1$ and $\forall x\ne0 . f(x)=0$,

$g(1)=0$ and $\forall x\ne1 . g(x)=1$.

Then you can easily show that $A \le_{M}B$ (using $f$) and $B \le_{M}A$ (using $g$) but obviously $A\ne B$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.