Question

Let be two disjoint languages. Say that language separates if $A\subseteq CandB\subseteq C\text{'}$. Describe two disjoint Turing-recognizable languages that aren’t separable by any decidable language.

Short answer

There are two Turing Recognizable language are disjoint is proved.

Step-by-step solution

Turing Recognizable

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e., TM halt and accept strings belong to language L and will reject or not halt on the input strings that doesn’t belong to language L.

Proving there are two Turing Recognizable language are disjoint.

Let us consider a Turing Machine which will act as decider for C which is acting as separator between A and B. Now we assume decide respectively. We will construct a Turing Machine S that based on Turing Machine C as follows:

$S=oninput‹M,w›$

$$\begin{gathered} (Run‹M_1,w›and‹M_2,w› \\ If{M}_{1}acceptsÞMrejects \\ And \\ If{M}_{2}acceptsÞMrejects \end{gathered}$$

It is to be noted that M will always halt in every situation, where C decides A and B.

Thus, no decidable language could be used to separate two disjoint Turing-recognizable languages.