# On the language of Turing machines that accepts 1 but does not accept 0

I need to find the find the minimal class $$\mathcal{L}$$ belongs to where

$$\mathcal{L} = \{\langle M \rangle: M \text{ is a TM that accepts 1 but does not accept 0}\}.$$

I think I can prove that $$\mathcal{L}\in \overline{\mathsf{RE}\cup\mathsf{co{-}RE}}$$ using 2 mapping reductions from $$\text{ACC}$$ ($$M$$ is TM that accept $$w$$) and $$\overline{\text{ACC}}$$ respectively. But I also know that

$$\hat{L}=\{ \langle M_1,w_1,M_2,w_2\rangle : w_1 \in L(M_1) \wedge w_2 \notin L(M_2)\}\in \overline{\mathsf{RE}\cup\mathsf{co{-}RE}}$$

My question is whether it is possible to apply somehow reduction from $$\hat{L}$$ to $$\mathcal{L}$$ ? or am I missing something...

Yes, we can reduce $$\hat L$$ to $$\mathcal L$$ as you suspected. Imagine we replace $$1$$ by $$w_1$$ and $$0$$ by $$w_2$$.

Let $$s=\langle M_1,w_1,M_2,w_2\rangle$$, where $$M_1, M_2$$ are Turing machines and $$w_1, w_2$$ are strings. Construct Turing machine $$T_s$$ such that given input $$w$$, $$T_s$$ will check whether $$w$$ is $$0$$ or $$1$$.

• if $$w=0$$, $$T_s$$ will simulate $$M_2$$ with input $$w_2$$ exactly.
• if $$w=1$$, $$T_s$$ will simulate $$M_1$$ with input $$w_1$$ exactly.
• if $$w$$ is not $$0$$ nor $$1$$, $$T_s$$ will accept immediately.

If $$s\in\hat L$$, it is clear that $$T_s\in\mathcal L$$. If $$s\not\in\hat L$$, it is clear that $$T_s\not\in\mathcal L$$.

The map $$t$$ that maps a string $$s$$

• to $$\langle T_s\rangle$$ if $$s$$ is the encoding of some $$M_1, w_1, M_2, w_2$$ and
• to $$\langle\text{acc}\rangle$$ otherwise, where $$\text{acc}$$ is the Turing machine that just accepts upon every input (hence, $$\langle\text{acc}\rangle\not\in\mathcal L\,$$).

is a Turing reduction from $$\hat L$$ to $$\mathcal L$$.