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

Question

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

Answer 1

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