Question

Let A and B be two disjoint languages. Say that language C separates A and B if $\mathit{A}\mathbf{\subseteq }\mathit{C}$and $\mathit{B}\mathbf{\subseteq }\mathit{C}$. Show that any two-disjoint co-Turing-recognizable languages are separable by some decidable language.

Short answer

Two-disjoint co-Turing-recognizable languages are separable by some decidable language.

Step-by-step solution

Decidable language

A decidable language is decided by a Turing machine that accepts the inputs of a language.

Show that any two-disjoint co-Turing-recognizable languages are separable by some decidable language

Let A and B be two disjoint languages. Consider that the language C separates A and B if $A\subseteq C$and $B\subseteq C.$Any two disjoint co-RE languages that are separable by some decidable language can be shown as follows:

Ais in RE, and M₁ semi-decides it.

Bis in RE, and M₂ semi-decides it.

The languageCcan be described by a Turing Machine M that decides:

Mon input w

Run M₁ and M₂ on w(in interleaved mode).

If M₁ accepts, Mrejects; If M₂ accepts, Maccepts.

Notice that M always halts; this shows that C=LM.

Therefore, it has been shown that any two-disjoint co-Turing-recognizable languages are separable by some decidable language.