how does Kleene-Post show two languages that are not Turing reducible to each other? I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument.
I've seen it in many places: for example a very brief summary here (where it is used to answer a different question about mapping reducibility), and also in page 2 here and also page 40 of here. There's also a prior thread on Kleene-Post, but that asks something very specific about one component of Kleene-Post, not how the entire proof works.
Very roughly speaking, it seems to be something about constructing a pair of sequences of languages (or sequence of sets of languages, I'm not too sure) such that for each &quot;step&quot; in the sequence, there's at least one oracle TM (i.e. a TM that is able to query some oracle) for which an oracle for one &quot;side&quot; cannot be used to decide the other &quot;side&quot;. Once these sequences are done, we take the intersection of every element in the sequence, and by construction all the languages in this intersection will fail to be mutually Turing reducible by every single possible oracle TM.
While I believe the general argument follows the above, I don't understand the details at all, since the proofs I've linked to use terminology (e.g. recursive, characteristic function, etc.) that differs significantly from those used by Sipser, the textbook I'm following (e.g. Turing recognizable, Turing decidable). There's also a few other proofs I've seen which I have not linked, and in those proofs I found the notation and exposition still difficult to understand.
My question is: how does the Kleene-Post proof work? What are the details of the construction, presented carefully in a way that is unambiguous and easily understood, preferably using terminology from Sipser as opposed to equivalent but different terminology?
Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T_0,T_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\Sigma$. I will denote by $T_i^O(x)$ the output of the execution of $T_i$ on input $x$ with oracle $O$, or $\bot$ if the machine doesn't halt. We say that $T_i$ (Turing-)reduces $A$ to $B$ if $T_i^B(x)$ halts for all $x$, and returns the truth value of &quot;$x \in A$&quot;. We assume for simplicity that the output of $T_i^B(x)$ can always be interpreted as a truth value.
We will construct two sequences $A_0,A_1,\ldots$ and $B_0,B_1,\ldots$ of &quot;partial sets&quot;, that is, mappings from $\Sigma^*$ to $\{0,1,\bot\}$. Initially, $A_0$ and $B_0$ map all strings in $\Sigma^*$ to $\bot$. Moreover, $A_{i+1}$ is an extension of $A_i$, that is, if $A_i(x)\neq \bot$ then $A_{i+1}(x) = A_i(x)$. Furthermore, each $A_i$ or $B_i$ is defined (not equal to $\bot$) for only finitely many words in $\Sigma^*$.
We will eventually take $A$ to be a set extending all $A_i$, that is, if $A_i(x) = 0$ for some $i$ then $i \notin A$; if $A_i(x) = 1$ for some $i$ then $i \in A$; and otherwise the status of $i$ doesn't matter (for definiteness, let $i \notin A$). The extension property guarantees that $A$ is well-defined. We define $B$ similarly.
We construct $A_{2i+1},B_{2i+1}$ from $A_{2i},B_{2i}$ in a way which rules out $T_i$ being a reduction from $A$ to $B$. By assumption, there exists $x \in \Sigma^*$ such that $A_{2i}(x) = \bot$. Consider what happens when we try to run $T_i$ on input $x$ with oracle $B_{2i}$. If $T_i$ tries to apply the oracle on a word $y$ on which $B_{2i}$ is defined, then it gets $B_{2i}(y)$. If $B_{2i}(y) = \bot$, then we simulate both branches in parallel (each of them could further split down the road). One of the following must happen:

There is a branch on which computation halts.
All branches result in non-halting computations.

The second case is easy – $T_i$ cannot be a reduction from $A$ to $B$, since it doesn't halt on input $x$, whatever happens in later stages of the construction. So we take $A_{2i+1} = A_{2i}$ and $B_{2i+1} = B_{2i}$.
In the first case, we actually have to do something. Pick a halting branch. The branch corresponds to a choice of definite values for some strings in $\Sigma^*$ on which $B_{2i}$ is undefined. We form $B_{2i+1}$ from $B_{2i}$ by keeping all values already defined in $B_{2i}$, and defining the additional strings occurring in the halting branch according to the branch. We form $A_{2i+1}$ from $A_{2i}$ by keeping all values already defined in $A_{2i}$, and defining $A_{2i+1}$ on $x$ in the opposite way to what $T_i$ answers in the halting branch: if $T_i$ outputs Yes then $A_{2i+1}(x) = 0$, and if $T_i$ outputs No then $A_{2i+1}(x) = 1$. This ensures that $T_i$ does not reduce $A$ to $B$, since it outputs the wrong value on $x$.
We construct $A_{2i+2},B_{2i+2}$ from $A_{2i+1},B_{2i+1}$ in a similar way, switching the roles of $A$ and $B$, ruling out $T_i$ being a reduction from $B$ to $A$.
Since the final $A$ and $B$ &quot;encompass&quot; all $A_i,B_i$, by construction no $T_i$ reduces $A$ to $B$ or $B$ to $A$, and so there is no Turing reduction from $A$ to $B$ or from $B$ to $A$.

The dichotomy above (some branch halts / all branches never halt) is not computable, in the sense that given $A_{2i},B_{2i},T_i$ we cannot determine which of the two options occurs. But it is possible using an oracle to the halting problem, since we can construct a Turing machine which tries out all branches in parallel, and immediately halts if one of them halts. Furthermore, by &quot;going down the tree&quot; we can find a halting branch if such exists. This shows that we can compute the sequences $A_i,B_i$ using an oracle to the halting problem.
Now suppose that when choosing a string $x$, then we always choose the first such string on which $A_{2i}$ (or $B_{2i+1}$) is undefined, according to some fixed ordering. This guarantees that any string will be eventually defined by some $A_i$ and by some $B_j$. Since the sequences $A_i,B_j$ are computable using an oracle to the halting problem, this shows that the sets $A,B$ are computable using an oracle to the halting problem.

Here is an alternative proof. Let $\mu$ be an arbitrary measure on languages such that $\mu(L) = 0$ for any specific language $L$ (we say that $\mu$ has no atoms). For example, $\mu$ could correspond to the experiment in which each word is put in the language with probability $1/2$ independently.
Let $\mathbf{A},\mathbf{B} \sim \mu$. The probability that $T_i$ reduces $\mathbf{A}$ to $\mathbf{B}$ is 0, since fixing the outcome of $\mathbf{B}$ to be $B$, there is at most one language $L$ which $T_i$ reduces to $B$, and by assumption $\mu(L) = 0$. Since there are only countably many machines $T_i$, it follows that the probability that $\mathbf{A}$ reduces to $\mathbf{B}$ is zero. Similarly, the probability that $\mathbf{B}$ reduces to $\mathbf{A}$ is 0. We conclude that almost surely (that is, with probability 1), $\mathbf{A}$ doesn't reduce to $\mathbf{B}$ and $\mathbf{B}$ doesn't reduce to $\mathbf{A}$. In particular, there exist realizations $A,B$ such that $A$ doesn't reduce to $B$ and $B$ doesn't reduce to $A$.