# Turing reduction problem, intersection is equal to an empty set

$L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)=\emptyset\}$ prove to be undecidable. My approach: We will prove this by reduction $L_{\emptyset} \leq_T L_c$ We begin by assuming that $L_c$ is decidable and that we have access to a black box $Q$ which decides it. We want to construct another Turing machine $H$ which decides $L_{\emptyset}$.

H = “On input (< M >, w).
Construct the following machine M’
M’ = “On input w.
Ignore input w and reject.
Run decider Q on (< M >,< M’>)
If Q accepts, reject.
If Q reject, accept.


I'm mainly concerned about my choice of $L_{\emptyset}$ (maybe $L_{halt}$ is better suited here?) and the part where I run the decider $Q$ on ($\langle M \rangle, \langle M'\rangle)$. Any help would be much appreciated, Thank you!

• Please don't delete questions after they have been answered. That's very impolite. – Raphael Nov 8 '17 at 18:57

Assume $L_c$ is decidable. We will reduce $A_{TM} =\{x\mid M_x \text{ halts on } x\}$ (the Halting problem language) to $L_c$. On input $x$ create a TM $M'$ which halts on only $x$. Then $L(M') = \{x\}$ and $M_x$ halts on $x$ iff $L(M_x) \cap L(M') = \{x\} \neq \emptyset$ iff $\left(\langle M_x \rangle, \langle M' \rangle \right) \notin L_c$. Thus, to check if $M_x$ halts on $x$ we check if $\left(\langle M_x \rangle, \langle M' \rangle \right) \notin L_c$.