1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

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.