how does Kleene-Post show two languages that are not Turing reducible to each other?

Question

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 "step" 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 "side" cannot be used to decide the other "side". 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?

Answer 1

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 "$x \in A$". 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 "partial sets", 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:

1. There is a branch on which computation halts.
2. 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$ "encompass" 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 "going down the tree" 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$.

Answer 2

(For the below, I referred extensively to this github repo as well as private communication with @aozgaa)

Languages can be represented as infinite-length bitstrings (ILB). We will use the two interchangeably. We will also represent strings meant to be inputs to TMs as integers, where a 1 bit in position $w$ in an ILB $A$ means that the $w$th string in $\Sigma^\star$ is a member of the language $A$.

Let $X$ and $Y$ be finite-length bitstrings (FLB). Let $P$ be an oracle TM, and $P^A$ means $P$ with an $A$ oracle "plugged in".

Let $Z(X)$ be the set of all ILBs with prefix $X$.

Claim 1:

There exists an FLB $X^\prime$ with $X$ as a prefix such that for any $A$ in $Z(X^\prime)$, $P^A$ satisfies at least one of the following: either 1. it cannot decide any language in $Z(Y0)$ or 2. it cannot decide any language in $Z(Y1)$.

Proof:

Consider all $A$ in $Z(X)$. Suppose there exists no $A$ for which $P^A$ halts on input $1 + |Y|$. Then, the claim is already true for $X^\prime = X$, since $P^A$ cannot be a decider for any language if there exists an input for which it never halts.

Otherwise, let $A^\prime$ be some $A$ for which $P^A$ halted. Look at the computation history of $P^{A^\prime}$, which may have calls to the $A^\prime$ oracle as a subroutine. The inputs $w$ to that subroutine may be any string, not necessarily the input $1 + |Y|$ itself.

Since $P^{A^\prime}$ halted, let $w^\prime$ be the highest input encountered by the $A^\prime$ oracle during the computation history. This means that $P^{A^\prime}$ does not care about any bits of $A^\prime$ after the $w^\prime$th. Thus, choose $X^\prime$ to be the first $w^\prime$ bits in $A^\prime$ (if the $A^\prime$ oracle is never actually called and there are no $w$, then just choose $X^\prime = X$), and thus for any $A$ in $Z(X^\prime)$, $P^A$ will halt on input $1 + |Y|$ with the same result as $P^{A^\prime}$.

Now consider the result itself: if it is "accept", then for any $A$ in $Z(X^\prime)$, $P^A$ will give the opposite result as (and thus cannot decide) any language in $Z(Y0)$. Conversely, if the result is "reject", then for any $A$ in $Z(X^\prime)$, $P^A$ will give the opposite result as any language in $Z(Y1)$. Either way, this $X^\prime$ satisfies the claim.

Main result:

There exist two infinite-length bitstrings $A$ and $B$ for which every possible oracle TM $P$ satisfies the following: $P^A$ does not decide $B$ and $P^B$ does not decide $A$.

Proof:

Begin with $X$ and $Y$ both the empty bitstring. Let $P_0$ be the lexicographically (or any other ordering, it doesn't matter) earliest of all possible oracle TMs. Using claim 1, extend $X$ and $Y$ to $X^\prime$ and either $Y^\prime = 0$ or $Y^\prime = 1$ such that for any $A$ in $Z(X^\prime)$, $P_0^A$ cannot decide any language in $Z(Y^\prime)$. Next, reuse claim 1 on $Y^\prime$ and $X^\prime$ (i.e. in the opposite order from before) and find $Y^{\prime \prime}$ and $X^{\prime \prime}$ such that for any $B$ in $Z(Y^{\prime \prime})$, $P_0^B$ cannot decide any language in $Z(X^{\prime \prime})$.

Note that $Z(X^{\prime \prime}) \subseteq Z(X^\prime)$ and $Z(Y^{\prime \prime}) \subseteq Z(Y^\prime)$, so the condition from earlier still holds: for any $A$ in $Z(X^{\prime \prime})$, $P_0^A$ cannot decide any language in $Z(Y^{\prime \prime})$

Now rename these new prefixes $X^{\prime \prime}$ and $Y^{\prime \prime}$ back into $X$ and $Y$, and starting with these new $X$ and $Y$ (that may now be non-empty), repeat the above for all the other oracle TMs $P_1$, $P_2$ and so on in (lexicographical or whatever) order, and continually extend the prefixes $X$ and $Y$. By construction, all of decidability properties of $P_i$ from past iterations are preserved since by extending prefixes, we never leave the $Z(X)$ and $Z(Y)$ from past iterations.

Hence, this diagonalization argument can proceed indefinitely and construct arbitrarily long prefixes $X$ and $Y$ such that for any $P$ in the first $n$ oracle TMs (with $n$ arbitrarily large) and any $A$ in $Z(X)$ and $B$ in $Z(Y)$, we have $P^A$ does not decide $B$ and $P^B$ does not decide $A$.