[proofplan] We build a descending sequence of infinite computable subtrees of $T$, using $\varnothing'$ to decide at stage $e$ whether the $e$-th oracle computation can be avoided on all paths through a further infinite subtree. If it can be avoided, we prune to that subtree; if it cannot, then every path through the current tree makes the computation halt. A path through all the subtrees is then chosen by a finite-branching argument, and the recorded stage decisions compute its jump from $\varnothing'$. The converse reduction $\varnothing' \le_T P'$ is the uniform reduction of the ordinary halting problem to every oracle jump. [/proofplan] [step:Define finite halting evidence for oracle computations] Fix a standard acceptable enumeration $(\Phi_e^X)_{e \in \mathbb N}$ of oracle Turing machines, where $X \in 2^{\mathbb N}$. For a finite binary string $\tau \in 2^{<\mathbb N}$, let $|\tau|$ denote its length, and write $\rho \preceq \tau$ when $\rho$ is an initial segment of $\tau$. For each $e \in \mathbb N$, define a decidable predicate $H_e(\tau)$ on finite binary strings as follows: $H_e(\tau)$ holds if the computation $\Phi_e^\tau(e)$ halts within at most $|\tau|$ steps, and during those steps every oracle query is to a number strictly smaller than $|\tau|$, so that the query is answered by the finite oracle $\tau$. This predicate is decidable because it only requires simulating finitely many computation steps and checking finitely many oracle queries. It has the following permanence property: if $H_e(\tau)$ holds and $X \in 2^{\mathbb N}$ extends $\tau$, then $\Phi_e^X(e)\downarrow$. Conversely, if $\Phi_e^X(e)\downarrow$, then there exists $n \in \mathbb N$ such that $H_e(X\upharpoonright n)$ holds, namely any $n$ larger than both the computation time and all oracle queries used before halting. [/step] [step:Prune an infinite computable tree to decide one jump question] Let $A \subseteq 2^{<\mathbb N}$ be an infinite computable binary tree, and fix $e \in \mathbb N$. Define the $e$-avoidance subtree \begin{align*} A_e := \{\tau \in A : \text{for every } \rho \preceq \tau,\ H_e(\rho) \text{ does not hold}\}. \end{align*} Since $A$ is computable and $H_e$ is decidable, $A_e$ is a computable tree. The set $A_e$ is finite iff there exists $m \in \mathbb N$ such that no string in $A_e$ has length $m$. The condition “there is no string of length $m$ in $A_e$” is decidable by finite search through $2^m$, so finiteness of $A_e$ is computably enumerable. Hence $\varnothing'$ decides whether $A_e$ is finite, and therefore also whether $A_e$ is infinite. If $A_e$ is infinite, then every path $Q \in 2^{\mathbb N}$ through $A_e$ satisfies $\Phi_e^Q(e)\uparrow$. Indeed, if $\Phi_e^Q(e)\downarrow$, the permanence property from the previous step gives $n \in \mathbb N$ such that $H_e(Q\upharpoonright n)$ holds, contradicting $Q\upharpoonright n \in A_e$. If $A_e$ is finite, then every path $Q \in 2^{\mathbb N}$ through $A$ satisfies $\Phi_e^Q(e)\downarrow$. Since $A_e$ is finite, choose $m \in \mathbb N$ such that no string of length $m$ lies in $A_e$. For any path $Q$ through $A$, the string $Q\upharpoonright m$ lies in $A$ but not in $A_e$, so some initial segment $\rho \preceq Q\upharpoonright m$ satisfies $H_e(\rho)$. By the permanence property, $\Phi_e^Q(e)\downarrow$. [guided] We want to make a decision about the single question “does $\Phi_e^Q(e)$ halt?” while still keeping at least one infinite path available. The finite predicate $H_e(\tau)$ records positive halting evidence that is already visible from the finite oracle $\tau$. Once such evidence appears, every infinite oracle extending $\tau$ gives the same halting computation. Given the current infinite computable tree $A$, define \begin{align*} A_e := \{\tau \in A : \text{for every } \rho \preceq \tau,\ H_e(\rho) \text{ does not hold}\}. \end{align*} Thus $A_e$ is obtained from $A$ by deleting every node below a finite string that already witnesses halting of $\Phi_e(e)$. This is a computable tree: membership in $A$ is decidable, the set of initial segments $\rho \preceq \tau$ is finite, and each assertion $H_e(\rho)$ is decidable by finite simulation. The key question is whether $A_e$ is still infinite. This is exactly the question $\varnothing'$ can answer. Since $A_e$ is finitely branching, $A_e$ is finite iff it has bounded height, equivalently iff \begin{align*} \exists m \in \mathbb N\ \text{such that no string } \tau \in A_e \text{ has length } m. \end{align*} For each fixed $m$, the statement “no string of length $m$ lies in $A_e$” is decidable by checking the finitely many strings in $2^m$. Therefore finiteness of $A_e$ is a computably enumerable property, and $\varnothing'$ decides it. There are now two cases. First suppose $A_e$ is infinite. Then any path $Q$ through $A_e$ avoids all finite halting evidence for the computation $\Phi_e^Q(e)$. If $\Phi_e^Q(e)$ did halt, then the computation would use only finitely many oracle bits and finitely many computation steps. Taking $n$ larger than both the use and the computation time would make $H_e(Q\upharpoonright n)$ true. But $Q\upharpoonright n \in A_e$, and membership in $A_e$ forbids $H_e$ on every initial segment. This contradiction proves $\Phi_e^Q(e)\uparrow$ for every path $Q$ through $A_e$. Second suppose $A_e$ is finite. Then $A_e$ has bounded height, so choose $m \in \mathbb N$ such that no string of length $m$ lies in $A_e$. Let $Q$ be any path through $A$. Since $Q\upharpoonright m \in A$ but $Q\upharpoonright m \notin A_e$, the definition of $A_e$ gives an initial segment $\rho \preceq Q\upharpoonright m$ with $H_e(\rho)$. This finite halting evidence persists to the infinite oracle $Q$, so $\Phi_e^Q(e)\downarrow$. Thus, in the finite case, the current tree $A$ already forces the $e$-th jump question to have answer yes on every path. [/guided] [/step] [step:Use $\varnothing'$ to build descending infinite computable trees] Define a sequence $(T_e)_{e \in \mathbb N}$ of infinite computable trees and a binary sequence $d: \mathbb N \to \{0,1\}$ by recursion. Let $T_0 := T$. Suppose $T_e$ has been defined and is an infinite computable tree. Form the avoidance subtree \begin{align*} (T_e)_e := \{\tau \in T_e : \text{for every } \rho \preceq \tau,\ H_e(\rho) \text{ does not hold}\}. \end{align*} Using $\varnothing'$, decide whether $(T_e)_e$ is infinite. If $(T_e)_e$ is infinite, set \begin{align*} T_{e+1} := (T_e)_e, \qquad d(e) := 0. \end{align*} If $(T_e)_e$ is finite, set \begin{align*} T_{e+1} := T_e, \qquad d(e) := 1. \end{align*} By the previous step, each $T_{e+1}$ is an infinite computable subtree of $T_e$. The construction is uniform relative to $\varnothing'$, so the decision sequence $d$ is computable from $\varnothing'$. [/step] [step:Choose a path through all the constructed trees] Define an auxiliary tree \begin{align*} R := \{\sigma \in 2^{<\mathbb N} : \sigma \in T_i \text{ for every } i \le |\sigma|\}. \end{align*} The tree $R$ is infinite. Indeed, fix $n \in \mathbb N$. Since $T_n$ is infinite, choose $\tau \in T_n$ with $|\tau| \ge n$. Let $\sigma := \tau\upharpoonright n$. Because the trees are descending, $T_n \subseteq T_i$ for every $i \le n$, and because each $T_i$ is closed under initial segments, $\sigma \in T_i$ for every $i \le n$. Hence $\sigma \in R$ and $|\sigma| = n$. Since $R$ is an infinite finitely branching binary tree, there exists $P \in 2^{\mathbb N}$ such that $P\upharpoonright n \in R$ for every $n \in \mathbb N$. For each fixed $i \in \mathbb N$ and each $n \ge i$, the definition of $R$ gives $P\upharpoonright n \in T_i$; closure under initial segments gives the same conclusion for $n < i$. Therefore $P$ is a path through every $T_i$, and in particular $P$ is a path through $T_0 = T$. [/step] [step:Compute the jump of the chosen path from $\varnothing'$] We prove that for every $e \in \mathbb N$, \begin{align*} e \in P' \iff d(e) = 1. \end{align*} If $d(e)=0$, then $T_{e+1}=(T_e)_e$, and $P$ is a path through $T_{e+1}$. By the avoidance case proved above, $\Phi_e^P(e)\uparrow$, so $e \notin P'$. If $d(e)=1$, then $(T_e)_e$ is finite, and $P$ is a path through $T_e$. By the finite avoidance case proved above, $\Phi_e^P(e)\downarrow$, so $e \in P'$. Thus $P' = \{e \in \mathbb N : d(e)=1\}$. Since $d \le_T \varnothing'$, we have $P' \le_T \varnothing'$. [/step] [step:Reduce the halting problem to the jump of the path] It remains to show $\varnothing' \le_T P'$. Fix a standard acceptable enumeration $(\varphi_e)_{e \in \mathbb N}$ of ordinary partial computable functions, where each $\varphi_e: \mathbb N \rightharpoonup \mathbb N$ is a partial map. Let \begin{align*} K := \{e \in \mathbb N : \varphi_e(e)\downarrow\} \end{align*} be the ordinary halting problem, so $K \equiv_T \varnothing'$. By acceptability of the oracle-machine enumeration, there is a total computable function $h: \mathbb N \to \mathbb N$ such that for every oracle $X \in 2^{\mathbb N}$ and every $e \in \mathbb N$, the oracle computation $\Phi_{h(e)}^X(h(e))$ ignores its oracle and simulates the ordinary computation $\varphi_e(e)$. Therefore \begin{align*} e \in K \iff \varphi_e(e)\downarrow \iff \Phi_{h(e)}^P(h(e))\downarrow \iff h(e) \in P'. \end{align*} Hence $K \le_m P'$, and therefore $\varnothing' \le_T P'$. Combining $P' \le_T \varnothing'$ with $\varnothing' \le_T P'$ gives $P' \equiv_T \varnothing'$. The path $P$ lies through the original tree $T$, so this completes the proof. [/step]