Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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.

The essential problem is the above and the last line where you said "I accept if I reached an x which satisfies the condition or I'm in infinite loop". How do you ever know that you are in an infinite loop. After running some Turing Machine for 1000 steps, how do you know that it wont halt on the 1001 step.

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.