# Unrecognizability of $L(M_1) \cap L(M_2) = \emptyset$

Let's define a language $$C = \{ \{M_1, M_2\} \mid M_1, M_2 \text{ are TMs s.t. } L(M_1) \cap L(M_2) = \emptyset \}$$

We have to show that $$C$$ is unrecognizable.

I am having trouble going on about with this proof. I am trying to do this by reduction, showing that this language is unrecognizable, but I am unsure on how to reduce this problem into a simpler problem.

• Turing machines cannot be unrecognizable. Languages can. – Yuval Filmus Apr 21 at 12:52
• @YuvalFilmus so how would you recommend to show the language is unrecognizable? im taking about the language not the turing machine, sorry for the confusion – fabio contreras Apr 21 at 12:58
• Reduce one of the standard unrecognizable languages to $C$. – Yuval Filmus Apr 21 at 12:59

Let $$T$$ be a Turing machine. Construct a Turing machine $$T'$$ that simulates $$T$$ on the empty input word and, when (if) the simulation ends, it accepts (regardless of the input to $$T'$$). Notice that $$T'$$ can be computed from $$T$$.

Pick $$M_2$$ as the Turing machine that immediately halts and accepts.

Then $$\{T', M_2\} \in C$$ iff $$L(T') = \emptyset$$, which happens iff $$T$$ does not halt on the empty input word. Therefore if $$C$$ were recognizable, the halting problem would be decidable (since the language of all Turing machines that halt on the empty input word is recognizable). This shows that $$C$$ is not recognizable.

Reduce from the acceptance problem using the following trick:

Let $$M_w$$ be the turing machine that accepts if and only if its input is $$w$$. Then $$L(M_w)=\{w\}$$.

Therefore, for any TM $$M$$ and word $$w$$,

$$\begin{matrix} \langle M,w\rangle \in ACCEPT_{TM} &\iff\\ w\in L(M)&\iff\\ L(M)\cap \{w\}\neq \emptyset &\iff\\ L(M)\cap L(M_w)\neq \emptyset &\iff\\ \langle M,M_w\rangle \notin C &\iff\\ \langle M, M_w\rangle \in \overline C\end{matrix}$$

Which means that the reduction defined by $$f(\langle M,w\rangle) = \langle M, M_w \rangle$$ is a reduction from the acceptence problem to $$\overline C$$, and thus $$C$$ is undecidable (since the acceptence is not in co-RE).

• thank you for the response but the question is asking to show C is unrecognizable not undecidable – fabio contreras Apr 21 at 14:51
• Yes, my bad. I fixed the answer (it is a correct reduction to the complement of $C$, not to $C$ itself) – nir shahar Apr 21 at 14:54