$A_{TM} = \{<M,w> | $ M is a TM and M accepts w $\}$

$H_{TM} = \{<M,w> | $ M is a TM and M halts on w $\}$

I thought that $L = H_{TM} \cap \overline{A_{TM}} \in R$

But I saw the proof for why $L \in RE \setminus R$

But I don't understand why this is wrong:

$H_{TM} \in RE$ and $\overline{A_{TM}} \in Co-RE $

We know that $RE \cap Co-RE = R$

So why is this wrong $L = H_{TM} \cap \overline{A_{TM}} \in RE \cap Co-RE = R$ ?


$RE$ and $co-RE$ are sets of sets of strings. $H_{TM}$ and $\overline{A_{TM}}$ are sets of strings. You correctly have that $H_{TM}\in RE$ and $\overline{A_{TM}}\in co-RE$. However, you cannot then conclude that $$ H_{TM}\cap\overline{A_{TM}}\in RE\cap co-RE $$ For a simple example, let $$ A=\{\{1\},\{2\}, \{1, 3\}, \{2, 3\}\}\text{ and }B=\{\{1\},\{3\}, \{1, 2\}, \{2, 3\}\} $$ So $A$ will serve as $RE$ and $B$ will serve as $co-RE$. Then we have $A\cap B=\{\{1\},\{2,3\}\}$. Now let $x=\{1,3\}\in A$ and $y=\{2,3\}\in B$ (here $x$ serves as $H_{TM}$ and $y$ serves as $\overline{A_{TM}}$). Then $x\cap y=\{3\}\notin A\cap B$.

| cite | improve this answer | |

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.