# Why does A=$\{\langle M_1,M_2,M_3 \rangle : L(M_1) \cap L(M_2) \ne L(M_3)\}$ isn't in $RE$.

I'm trying to figure out what's wrong with this following Turing machine which determinate that the following language

A=$\{\langle M_1,M_2,M_3 \rangle : L(M_1) \cap L(M_2) \ne L(M_3)\}$ is in $RE$.

I said that we can build a Turing machine that run all inputs in lexicography order,in parallel:

For an input $x$:

we run it on $M_1$ and $M_2$ if one of them rejected the input, we skip this input, and don't use it.

If both of them accepted:

we run $x$ on $M_3$ if it rejected we return $true$, if it accepted we skip this input and don't use it.

If we are in infinite: both $M_1$ and $M_2$ are in loop for checking $x$, or one of them accepted and the other in an infinite loop, or $M_3$ in infinite loop for checking $x$, if we reached this part, so the machine is infinite loop.

What is not correct? I accept if I reached an $x$ which satisfies the condition or I'm in infinite loop.

-

Suppose $M_1$ and $M_2$ are two Turing Machine that does not halt on anything. Suppose $M_3$ is a Turing Machine that halts only on some $x$.
If you run your algorithm and try test $\langle M_1, M_2, M_3 \rangle$ by running $M_1$ and $M_2$ on $x$. Here you algorithm would would not halt because $M_1$ and $M_2$ would not halt. Because $L(M_1) = L(M_2) = \emptyset$ and $L(M_3) = \{x\}$, you can not skip this step because this the only difference in the language.
However, the above only shows that your algorithm does not prove that show that $A$ is RE. You have not proven that $A$ is not RE.
To prove $A$ is not RE, one possible method is to reduce a language known to be not RE to $A$. Let $K$ denote the Halting Problem which is not computable. Let $\bar{K}$ be the complement of $K$. Hence $\bar{K}$ is not RE. Now reduce $\bar{K}$ to $A$. (I leave the detail to you.) Now if $A$ was RE, this reduction would prove that $\bar{K}$ is RE. Contradiction.
I wanted to show that the language is in $RE$, but I figured out that it doesn't so I showed my algorithm and asked how come it is not correct, since I believed it is correct and showing that the language is in RE because I showed an RE Turing machine, but I understand my mistakes. Regarding the "How do you know that you in an infinte loop"- I don't need to know that, if it accepts suitable inputs and infinte loop on unsuitable, it's fine for me, but I can see that it doesn't return true for your example, which it has to. Thanks a lot! – Joni Aug 5 '12 at 7:50