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.

  • $\begingroup$ Turing machines cannot be unrecognizable. Languages can. $\endgroup$ Apr 21 '21 at 12:52
  • $\begingroup$ @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 $\endgroup$ Apr 21 '21 at 12:58
  • $\begingroup$ Reduce one of the standard unrecognizable languages to $C$. $\endgroup$ Apr 21 '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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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