[proofplan] We use a finite-injury priority construction. Requirement $\mathcal R_e$ tries to diagonalize $B$ against $\Phi_e^A$ by choosing a witness $x$ and, if $\Phi_e^A(x)$ converges to $0$, enumerating $x$ into $B$ while restraining future changes in $A$ below the computation use. Requirement $\mathcal S_e$ acts symmetrically. The construction chooses witnesses above all relevant higher-priority restraints, cancels lower-priority strategies exactly when a new enumeration may have injured their protected computation, and then proves by induction on priority that each requirement is initialized only finitely many times and is eventually satisfied. [/proofplan] [step:Define the priority ordering and the finite records carried by each requirement] Let $(\mathcal T_i)_{i\in\mathbb N}$ denote the priority list \begin{align*} \mathcal T_{2e}=\mathcal R_e,\qquad \mathcal T_{2e+1}=\mathcal S_e. \end{align*} Lower index means higher priority. At each stage $s\in\mathbb N$, we define finite sets $A_s,B_s\subset\mathbb N$ and, for each requirement $\mathcal T_i$, a finite record. The record consists of either no witness, or one witness $x_i(s)\in\mathbb N$; and either no restraint, or one restraint $\rho_i(s)\in\mathbb N$. A restraint belonging to an $\mathcal R$-requirement restrains enumeration into $A$, because an $\mathcal R$-requirement protects a computation with oracle $A$. A restraint belonging to an $\mathcal S$-requirement restrains enumeration into $B$. We also keep a finite set $W_s\subset\mathbb N$ of all numbers that have ever been used as witnesses before or at stage $s$. A fresh witness at stage $s$ means an integer not in $W_s$. For each $e,s\in\mathbb N$ and each finite oracle approximation $C\subset\mathbb N$, define the stage-$s$ partial map \begin{align*} \Phi_{e,s}^{C}:\mathbb N &\rightharpoonup \{0,1\} \end{align*} by running the $e$th oracle Turing functional for at most $s$ steps with oracle answers from $C$ and declaring convergence exactly when that bounded simulation halts. Define $\Psi_{e,s}^{C}:\mathbb N\rightharpoonup\{0,1\}$ in the same way for the listing $(\Psi_e)_{e\in\mathbb N}$. The use of a convergent stage computation is the least $u\in\mathbb N$ such that every oracle query made during that computation is strictly below $u$; thus changing the oracle only at numbers $\geq u$ cannot affect the computation. [/step] [step:Construct the stage approximation while preserving restraints] Start with \begin{align*} A_0=B_0=W_0=\varnothing, \end{align*} and give every requirement no witness and no restraint. Assume that stage $s$ has produced $A_s$, $B_s$, $W_s$, and all records. At stage $s+1$, inspect only the finite initial segment \begin{align*} \mathcal T_0,\mathcal T_1,\dots,\mathcal T_s. \end{align*} First scan this finite initial segment in priority order and assign a fresh witness to every inspected requirement that currently has none. If $\mathcal T_i=\mathcal R_e$, choose its new witness $x_i(s+1)$ larger than every active restraint on $B$ imposed by a higher-priority $\mathcal S$-requirement and larger than every element of $W_s$. If $\mathcal T_i=\mathcal S_e$, choose its new witness $x_i(s+1)$ larger than every active restraint on $A$ imposed by a higher-priority $\mathcal R$-requirement and larger than every element of $W_s$. Add each newly assigned witness to $W_s$ as it is chosen; after this finite scan, call the resulting finite set of used witnesses $W_s'$. An inspected requirement is called ready at stage $s+1$ as follows. If $\mathcal T_i=\mathcal R_e$ has witness $x_i$ and $x_i\notin B_s$, then it is ready if the stage-$s$ computation \begin{align*} \Phi_{e,s}^{A_s}(x_i)=0 \end{align*} converges with some finite use $u$. If $\mathcal T_i=\mathcal S_e$ has witness $x_i$ and $x_i\notin A_s$, then it is ready if the stage-$s$ computation \begin{align*} \Psi_{e,s}^{B_s}(x_i)=0 \end{align*} converges with some finite use $u$. If no requirement is ready, set \begin{align*} A_{s+1}=A_s,\qquad B_{s+1}=B_s,\qquad W_{s+1}=W_s', \end{align*} and leave all records unchanged. If at least one requirement is ready, let $\mathcal T_i$ be the ready requirement of least index. If $\mathcal T_i=\mathcal R_e$ with witness $x_i$ and use $u$, define \begin{align*} B_{s+1}=B_s\cup\{x_i\},\qquad A_{s+1}=A_s, \end{align*} and set $\rho_i(s+1)=u$ as a restraint on $A$. Then initialize every inspected lower-priority requirement $\mathcal T_j$ with $i<j\leq s$ whose current record may have been made unreliable: delete its witness and its restraint if either it is an $\mathcal S$-requirement with witness below $u$, or it has a protected computation using oracle $B$ with recorded use strictly larger than $x_i$. Leave all other lower-priority records unchanged. If $\mathcal T_i=\mathcal S_e$ with witness $x_i$ and use $u$, define \begin{align*} A_{s+1}=A_s\cup\{x_i\},\qquad B_{s+1}=B_s, \end{align*} and set $\rho_i(s+1)=u$ as a restraint on $B$. Then initialize every inspected lower-priority requirement $\mathcal T_j$ with $i<j\leq s$ whose current record may have been made unreliable: delete its witness and its restraint if either it is an $\mathcal R$-requirement with witness below $u$, or it has a protected computation using oracle $A$ with recorded use strictly larger than $x_i$. Leave all other lower-priority records unchanged. In both cases set $W_{s+1}=W_s'$. [/step] [step:Verify that the construction defines computably enumerable sets] At stage $s+1$ the construction inspects only the finite list $\mathcal T_0,\dots,\mathcal T_s$, changes only records in that list, and enumerates at most one integer into one of $A$ and $B$. The predicates \begin{align*} \Phi_{e,s}^{A_s}(x)=0,\qquad \Psi_{e,s}^{B_s}(x)=0 \end{align*} are decidable from the finite stage-$s$ simulations and the finite oracle approximations $A_s$ and $B_s$. Therefore the maps $s\mapsto A_s$ and $s\mapsto B_s$ are effective increasing finite approximations. Define \begin{align*} A=\bigcup_{s=0}^{\infty} A_s,\qquad B=\bigcup_{s=0}^{\infty} B_s. \end{align*} Since membership is enumerated stage by stage by an effective procedure, $A$ and $B$ are computably enumerable. [guided] The construction is algorithmic because every decision made at stage $s+1$ is based on finite data. At that stage we inspect only $\mathcal T_0,\dots,\mathcal T_s$. The sets $A_s$ and $B_s$ are finite, each inspected requirement has at most one witness and one restraint, and a stage-$s$ computation means a bounded simulation: run the relevant oracle machine for at most $s$ steps and answer oracle queries using the finite oracle approximation available at stage $s$. Thus, for each fixed stage, we can effectively decide which inspected requirements are ready. If a ready inspected requirement exists, we act only for the least such requirement, enumerate one number into either $A$ or $B$, and delete finitely many lower-priority records among the inspected requirements. If no inspected requirement is ready, no number is enumerated. Hence the increasing sequences \begin{align*} A_0\subset A_1\subset A_2\subset\cdots,\qquad B_0\subset B_1\subset B_2\subset\cdots \end{align*} are computably generated. Their unions \begin{align*} A=\bigcup_{s=0}^{\infty} A_s,\qquad B=\bigcup_{s=0}^{\infty} B_s \end{align*} are therefore computably enumerable sets. [/guided] [/step] [step:Show that protected computations are preserved unless explicitly initialized] Consider an $\mathcal R_e$-requirement whose record at some stage contains witness $x$ and restraint $u$ imposed after observing \begin{align*} \Phi_{e,s}^{A_s}(x)=0 \end{align*} with use $u$. If this record is never later initialized, then no later enumeration into $A$ occurs below $u$. Indeed, any higher-priority enumeration into $A$ below $u$ would, by the construction, initialize the record because the protected computation uses oracle $A$ with recorded use $u$. Any lower-priority enumeration into $A$ is chosen above all active higher-priority restraints on $A$, including $u$, and hence cannot occur below $u$. Therefore the oracle $A$ is unchanged below $u$ after stage $s$, and the computation is stable: \begin{align*} \Phi_e^A(x)=0. \end{align*} The same argument with $A,\Phi,\mathcal R$ interchanged with $B,\Psi,\mathcal S$ shows that an uninitialized protected $\mathcal S_e$-computation \begin{align*} \Psi_{e,s}^{B_s}(x)=0 \end{align*} with use $u$ remains true in the limit: \begin{align*} \Psi_e^B(x)=0. \end{align*} [/step] [step:Prove by induction on priority that every requirement is initialized finitely often] We prove by induction on $i$ that $\mathcal T_i$ is initialized only finitely many times. Assume every higher-priority requirement $\mathcal T_j$ with $j<i$ is initialized only finitely many times. Since a requirement acts only when it has a witness and then either keeps a permanent restraint or is later initialized, each higher-priority requirement acts only finitely many times after its final initialization. Hence there is a stage $s_0$ after which no higher-priority requirement ever initializes $\mathcal T_i$. After stage $s_0$, if $\mathcal T_i$ has no witness, it receives a fresh witness at the next assignment phase. Once assigned, that witness can be lost only by initialization from a higher-priority action, and no such initialization occurs after $s_0$. Thus $\mathcal T_i$ eventually has a permanent witness. If it later acts, its restraint can be lost only by initialization from a higher-priority action, again impossible after $s_0$. Therefore $\mathcal T_i$ is initialized only finitely many times. By induction over $i\in\mathbb N$, every requirement is initialized only finitely many times. [/step] [step:Satisfy each diagonalization requirement] Fix $e\in\mathbb N$. We prove $\mathcal R_e$, namely $B\neq \Phi_e^A$. Let $i=2e$, so $\mathcal T_i=\mathcal R_e$. By the previous step, $\mathcal R_e$ has a final witness; denote it by $x\in\mathbb N$. After its last initialization, $x$ is never used as a witness for any other requirement, and the only requirement allowed to enumerate $x$ into $B$ is $\mathcal R_e$ itself. There are two cases. If $\mathcal R_e$ eventually acts with witness $x$, then it enumerates $x$ into $B$ after observing a computation \begin{align*} \Phi_{e,s}^{A_s}(x)=0 \end{align*} with some finite use $u$. Since this is the final record of $\mathcal R_e$, the protected computation is not later initialized. By preservation of protected computations, \begin{align*} \Phi_e^A(x)=0. \end{align*} But $x\in B$, so \begin{align*} B(x)=1\neq 0=\Phi_e^A(x). \end{align*} Thus $B\neq \Phi_e^A$. If $\mathcal R_e$ never acts after receiving its final witness $x$, then $x\notin B$. Suppose for contradiction that $\Phi_e^A(x)=0$. Let $u\in\mathbb N$ be the use of this limiting computation, so the computation queries only oracle numbers below $u$. Since $A=\bigcup_s A_s$ is increasing and only finitely many numbers are below $u$, choose a stage $t_0$ after which $A_s\cap\{0,\dots,u-1\}=A\cap\{0,\dots,u-1\}$ for every $s\geq t_0$. Choose $t_1\geq t_0$ large enough that the bounded simulation sees the halting computation, so \begin{align*} \Phi_{e,t_1}^{A_{t_1}}(x)=0. \end{align*} By finite injury for the finitely many higher-priority requirements $\mathcal T_j$ with $j<i$, choose $t_2\geq t_1$ after their last action. For every stage $s+1\geq \max\{t_2,i+1\}$, the requirement $\mathcal R_e$ is inspected, still has witness $x$, and is ready. No higher-priority requirement can act at such a stage, by the choice of $t_2$. Therefore $\mathcal R_e$ is the least ready requirement and must act, contradicting the assumption that it never acts after receiving $x$. Therefore $\Phi_e^A(x)$ is either undefined or equal to $1$. Since $x\notin B$, we have \begin{align*} B(x)=0\neq \Phi_e^A(x) \end{align*} whenever $\Phi_e^A(x)$ is defined, and in particular $B$ is not equal to the total function $\Phi_e^A$. Now fix $e\in\mathbb N$ and prove $\mathcal S_e$, namely $A\neq\Psi_e^B$. Let $i=2e+1$, so $\mathcal T_i=\mathcal S_e$, and let $x\in\mathbb N$ be its final witness. If $\mathcal S_e$ acts with witness $x$, then it enumerates $x$ into $A$ after observing \begin{align*} \Psi_{e,s}^{B_s}(x)=0 \end{align*} with some finite use. Since the final protected computation is never initialized, preservation gives \begin{align*} \Psi_e^B(x)=0. \end{align*} But $x\in A$, so $A(x)=1\neq 0=\Psi_e^B(x)$. If $\mathcal S_e$ never acts after receiving its final witness $x$, then $x\notin A$. Suppose for contradiction that $\Psi_e^B(x)=0$, and let $u\in\mathbb N$ be the use of this limiting computation. Choose a stage $t_0$ after which $B_s\cap\{0,\dots,u-1\}=B\cap\{0,\dots,u-1\}$ for every $s\geq t_0$, choose $t_1\geq t_0$ large enough that \begin{align*} \Psi_{e,t_1}^{B_{t_1}}(x)=0, \end{align*} and choose $t_2\geq t_1$ after the last action of every higher-priority requirement $\mathcal T_j$ with $j<i$. For every stage $s+1\geq \max\{t_2,i+1\}$, the requirement $\mathcal S_e$ is inspected, still has witness $x$, and is ready; no higher-priority requirement can act. Hence $\mathcal S_e$ must act, a contradiction. Therefore $\Psi_e^B(x)$ is either undefined or equal to $1$. Since $x\notin A$, this gives $A\neq\Psi_e^B$. [/step] [step:Conclude Turing incomparability] For every $e\in\mathbb N$, the requirement $\mathcal R_e$ gives \begin{align*} B\neq \Phi_e^A, \end{align*} and the requirement $\mathcal S_e$ gives \begin{align*} A\neq \Psi_e^B. \end{align*} Since $(\Phi_e)_{e\in\mathbb N}$ and $(\Psi_e)_{e\in\mathbb N}$ are effective listings of all oracle Turing functionals, no oracle computation from $A$ computes $B$, and no oracle computation from $B$ computes $A$. Therefore \begin{align*} B\nleq_T A,\qquad A\nleq_T B. \end{align*} The computably enumerable sets $A$ and $B$ constructed above satisfy all requirements $\mathcal R_e$ and $\mathcal S_e$, completing the proof. [/step]