4
$\begingroup$

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 ?

Improve this question
$\endgroup$
1
  • $\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$ Commented Nov 25, 2017 at 19:17

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 25, 2017 at 19:27

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.