Theorem. Computably (recursively) inseparable sets [FW2E]

Consider the following two subsets of the natural numbers:

A={n∈N∣ϕn(n) terminates with result 0}B={n∈N∣ϕn(n) terminates with result 1}\begin{gather*} A = \{ n \in \N \mid \phi_n(n)\text{ terminates with result }0 \} \\ B = \{ n \in \N \mid \phi_n(n)\text{ terminates with result }1 \} \end{gather*}

There is no Turing machine which terminates on all inputs and separates AA from BB.

Proof [local-0]

Suppose we are given a Turing machine ee terminates with result 00 or 11 on all inputs, such that e(n)=0e(n) = 0 when n∈An \in A and e(n)=1e(n) = 1 when n∈Bn \in B. Consider the algorithm FF that returns a Turing machine for a given natural number:halt(k)halt(k) is the machine that terminates with result kk on every input.

F(n):={halt(1) when e(n)=0halt(0) when e(n)=1F(n) := \begin{cases} halt(1) \text{ when } e(n) = 0 \\ halt(0) \text{ when } e(n) = 1 \end{cases}

Because ee terminates on all inputs, so does FF. By construction e(F(n))≠e(n)e(F(n)) \ne e(n) for each input nn: Consider the case that e(n)=0e(n) = 0, then F(n)=halt(1)F(n) = halt(1). halt(1)∈Bhalt(1) \in B because

ϕ⌜halt(1)⌝(⌜halt(1)⌝)=halt(1)(⌜halt(1)⌝)=1\phi_{\ulcorner halt(1) \urcorner}(\ulcorner halt(1) \urcorner) = halt(1)(\ulcorner halt(1) \urcorner) = 1

but then e(F(n))=e(halt(1))=1≠0=e(n)e(F(n)) = e(halt(1)) = 1 \ne 0 = e(n). The same argument applies to e(n)=1e(n) = 1.

By the second recursion theoremhttps://www.math.ucla.edu/~ynm/lectures/2009csl.pdf, there exists a Turing machine ff realizing FF applied to its own Gödel number, that is, ϕ⌜f⌝≃ϕ⌜F(f)⌝\phi_{\ulcorner f \urcorner} \simeq \phi_{\ulcorner F(f) \urcorner}. Because F(f)F(f) is halt(0)halt(0) or halt(1)halt(1), both constant, ϕ⌜f⌝\phi_{\ulcorner f \urcorner} is constant as well, say with value kk. Hence

ϕ⌜f⌝(⌜f⌝)=k=ϕ⌜F(f)⌝(⌜F(f)⌝)\phi_{\ulcorner f \urcorner}(\ulcorner f \urcorner) = k = \phi_{\ulcorner F(f) \urcorner}(\ulcorner F(f) \urcorner)

so either both ff and F(f)F(f) lie in AA, or both lie in BB. In either case e(f)=e(F(f))e(f) = e(F(f)). However, e(n)≠e(F(n))e(n) \ne e(F(n)) for all nn.