Let the language $L$ be as follow ;

$$L=\{\langle M_1 \rangle \langle M_2 \rangle \mid L(M_1) \cap L(M_2)=\emptyset \}$$

$\langle M_1 \rangle$ and $\langle M_2 \rangle$ are the encoding of the Turing machine $M_1$ and $ M_2$.

Using Reduction, I have to prove that $L$ is not recursively enumerable.

In order to prove that I have to find a non-recursively enumerable language $S$ so that: $$S \leq L$$ One of the non recursively enumerable that I had in my lesson, were those : $${H_{\varepsilon}^\complement}=\{\langle M \rangle \mid \text{M does not halt on empty input} \}$$ and ; $${H_{all}}=\{ \langle M \rangle \mid \text{M halts on each input} \}$$

$$ \text{Let then } S = {H_{all}}$$

I have to prove in this case that ; $${H_{all}} \leq L $$

let then ; $$ f : {H_{all}} \rightarrow L \\ \langle M \rangle \mapsto \langle M \rangle \langle M^\complement \rangle$$

In this case $M^\complement $ simulate M in each input , when $M$ accepts/rejects, $M^\complement $ rejects/accepts.

$\texttt{case 1}$

$\langle M \rangle \in {H_{all}} \Rightarrow \text{M halts on each input and accepts/rejects} \Rightarrow M^\complement\text{ hatls on each input and rejects/accepts} \Rightarrow L(M) \cap L(M^\complement)= \emptyset $

$\Rightarrow \langle M \rangle \langle M^\complement \rangle \in L $

$\texttt{case 2}$

$\langle M \rangle \not\in {H_{all}} \Rightarrow \text{M does not halt on all inputs} \Rightarrow M^\complement\text{ halts on some inputs} \Rightarrow L(M) \cap L(M^\complement) \neq\emptyset $

$\Rightarrow \langle M \rangle \langle M^\complement \rangle \not\in L $

somehow i think , the contruction of the function of is not right, does anyone maybe have an other idea or an other S to choose ?

  • $\begingroup$ It is not clear how you create $M^C$ assuming you define $M^C$ to be a TM recognizing the complement of $L(M)$. Let $L(M)$ be a recursively enumerable which is not recursive. Then the complement of $L(M)$ is not recursively enumerable and so $M^C$ does not exist. So, your solution may not work. $\endgroup$
    – fade2black
    Nov 25, 2017 at 19:17

1 Answer 1


Assume that $L$ is recursively enumerable. We can reduce the Halting problem to $L$ as following. Given $\langle M, w \rangle$, create a TM $M'$ which halts only on the input $w$, and infinitely loops if the input is different from $w$. Clearly $L(M') = \{w\}$ and $L(M) \cap L(M') = \emptyset \iff \langle M,M' \rangle \in L \iff \langle M, w \rangle \notin HALT$. This shows that $\overline{HALT}$ is recursively enumerable. Since $HALT$ is also r.e. it follows that $HALT$ is decidable which is impossible. Thus $L$ is not recursively enumerable.

$HALT = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ halts on input } w \}$.

  • $\begingroup$ so if understand correctly , if $ f(<M,w))= M^{*}$ which is the Turing machine that only halt on w and otherwise loop forever . then we have $<M,w> \in H^\complement \Rightarrow \text{M does not halt on w, but M^* halts} \Rightarrow L(M) \cap L(M^*) =\emptyset$ $\endgroup$
    – Mohbenay
    Nov 25, 2017 at 19:19
  • $\begingroup$ $<M,w> \not\in H^\complement \Rightarrow <M,w> \in H \Rightarrow \text{M halts on w , and M^{*} halts} \Rightarrow L(M) \cap L(M^{*}) \neq \emptyset$ $\endgroup$
    – Mohbenay
    Nov 25, 2017 at 19:21
  • $\begingroup$ You don't need to use $H^C$. Moreover, $\langle M, w \rangle \in H^C$ does not imply that $M$ does not halt on $w$. My solution uses only the Halting problem to reach a contradiction. $\endgroup$
    – fade2black
    Nov 25, 2017 at 19:23
  • $\begingroup$ then we have $H^\complement \leq L$, and because $H^\complement $ not RE then L is not RE too $\endgroup$
    – Mohbenay
    Nov 25, 2017 at 19:25
  • $\begingroup$ yeah i know when $<M,w> \not \in H^\complement$ then M does not halt on w , or syntax of the encoding is wrong , i can manage that $\endgroup$
    – Mohbenay
    Nov 25, 2017 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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