$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!

  • 1
    $\begingroup$ Please don't delete questions after they have been answered. That's very impolite. $\endgroup$
    – Raphael
    Nov 8, 2017 at 18:57

1 Answer 1


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


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.