[proofplan] We build a set $A \subseteq \mathbb{N}$ by Spector's perfect-tree construction. At stage $e$ we pass to a computable perfect subtree that decides the $e$-th Turing functional in one of two ways: either every total value computed from a path is computable, or the value computes the path back. Interleaving this with diagonalization against the $e$-th computable set makes $A$ noncomputable. The resulting degree is minimal because every noncomputable set below $A$ is equal in degree to $A$. [/proofplan] [step:Fix the effective notation for functionals and perfect trees] Let $(\Phi_e)_{e \in \mathbb{N}}$ be an effective enumeration of all [Turing functionals](/page/Turing%20Functional), where for each oracle $X \subseteq \mathbb{N}$ the partial map $\Phi_e^X: \mathbb{N} \rightharpoonup \mathbb{N}$ is the function computed by the $e$-th oracle machine with oracle $X$. For a finite binary string $\tau \in 2^{<\mathbb{N}}$, the notation $\Phi_e^\tau(n)=m$ means that the computation halts with value $m$, every oracle query made during the computation is below $|\tau|$, and each such query $q$ is answered by the bit $\tau(q)$. With this convention, if $\tau \subseteq \upsilon$ and $\Phi_e^\tau(n)$ halts, then $\Phi_e^\upsilon(n)=\Phi_e^\tau(n)$ by oracle-use monotonicity. Let $(C_e)_{e \in \mathbb{N}}$ be an effective enumeration of all partial computable maps $C_e: \mathbb{N} \rightharpoonup \{0,1\}$. For sets $B,A \subseteq \mathbb{N}$, write $B \leq_T A$ when $B$ is [Turing reducible](/page/Turing%20Reducibility) to $A$, meaning that $B=\Phi_e^A$ for some $e \in \mathbb{N}$ with total output. The [Turing degree](/page/Turing%20Degree) of $A$ is its equivalence class under mutual Turing reducibility, and a nonzero degree is minimal when no nonzero degree lies strictly below it. A [computable perfect tree](/page/Computable%20Perfect%20Tree) is represented by a computable map $T:2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ such that $T(\sigma) \subsetneq T(\tau)$ whenever $\sigma \subsetneq \tau$, and $T(\sigma0)$ and $T(\sigma1)$ are incompatible finite binary strings for every $\sigma \in 2^{<\mathbb{N}}$. Its path set is $[T] := \{X \subseteq \mathbb{N}: \text{for some }Y \in 2^{\mathbb{N}},\ X = \bigcup_{n=1}^{\infty} T(Y|n)\}$. A finite binary string $\tau$ lies inside $T$ if $\tau$ is comparable by extension with some node $T(\sigma)$ and is compatible with a path in $[T]$; equivalently, $\tau$ is an initial segment of some $X \in [T]$ or is extended by such an initial segment. This relation is decidable from the computable representation of $T$ by searching the finite splitting structure up to length at least $|\tau|$. If $S$ and $T$ are computable perfect trees, write $S \preceq T$ when $[S] \subseteq [T]$. [/step] [step:Prove the splitting dichotomy for one Turing functional] [claim:Splitting dichotomy] Let $T:2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ be a computable perfect tree and let $e \in \mathbb{N}$. There is a computable perfect subtree $S \preceq T$ such that exactly one of the following alternatives holds. First, $S$ is $e$-splitting: for every $\sigma \in 2^{<\mathbb{N}}$, there is an input $n \in \mathbb{N}$ for which $\Phi_e^{S(\sigma0)}(n)$ and $\Phi_e^{S(\sigma1)}(n)$ both converge and have different values. Second, $S$ is $e$-nonsplitting: no two incompatible finite strings extending the stem $S(\varnothing)$ inside $T$ give a finite disagreement for $\Phi_e$. [/claim] [proof] For finite binary strings $\alpha$ and $\beta$ lying inside $T$, say that $\alpha$ and $\beta$ $e$-split when they are incompatible and there is an input $n \in \mathbb{N}$ such that $\Phi_e^\alpha(n)$ and $\Phi_e^\beta(n)$ both halt and are unequal. This relation is computably enumerable because halting computations with finite oracles have finite use. If every range node of $T$ has two incompatible finite extensions inside $T$ that $e$-split, build $S$ recursively. Having chosen $S(\sigma)$ as a range node of $T$, search through finite strings inside $T$ extending $S(\sigma)$ until finding incompatible extensions $\alpha_0$ and $\alpha_1$ that $e$-split. Then search for range nodes $\beta_0$ and $\beta_1$ of $T$ such that $\alpha_i \subseteq \beta_i$ for each $i \in \{0,1\}$, and define $S(\sigma0):=\beta_0$ and $S(\sigma1):=\beta_1$. The second search terminates because each $\alpha_i$ lies inside $T$ and is compatible with a path in $[T]$, so some later range node of $T$ extends it. The first search is effective because membership of finite strings inside $T$ is decidable and the finite-oracle halting relation is computably enumerable, and it terminates by the present case assumption. Oracle-use monotonicity transfers the finite disagreement from $\alpha_0,\alpha_1$ to $\beta_0,\beta_1$. Thus this recursive construction makes $S$ a computable perfect subtree of $T$ with $[S] \subseteq [T]$, and the chosen range-node successors give the finite disagreement required for $S$ to be $e$-splitting. If the preceding case fails, there is a range node $\rho=T(\gamma)$, for some $\gamma \in 2^{<\mathbb{N}}$, such that no two incompatible finite extensions of $\rho$ inside $T$ $e$-split. Define a computable perfect subtree $S:2^{<\mathbb{N}}\to 2^{<\mathbb{N}}$ by $S(\sigma):=T(\gamma\sigma)$, where $\gamma\sigma$ denotes concatenation. Then $S(\varnothing)=\rho$, $S \preceq T$, and by the choice of $\rho$ no two incompatible finite strings extending $S(\varnothing)=\rho$ inside $T$ give a finite disagreement for $\Phi_e$. Thus $S$ is $e$-nonsplitting. [/proof] [/step] [step:Extract the computational consequence of each side of the dichotomy] [claim:Recovery or computability] Let $S$ be the computable perfect tree supplied by the splitting dichotomy for $T$ and $e$. If $S$ is $e$-splitting and $A \in [S]$ with $\Phi_e^A$ total, then $A \leq_T \Phi_e^A$. If $S$ is $e$-nonsplitting and $A \in [S]$ with $\Phi_e^A$ total, then $\Phi_e^A$ is computable. [/claim] [proof] Assume first that $S$ is $e$-splitting. Let $B:=\Phi_e^A$ be the total function computed from $A$. Since $A \in [S]$, there is a unique path $Y \in 2^{\mathbb{N}}$ with $A=\bigcup_{n=1}^{\infty}S(Y|n)$. We compute $Y$ from $B$ by induction on its initial segments. Suppose $Y|k$ has been computed. The strings $S((Y|k)0)$ and $S((Y|k)1)$ themselves have $\Phi_e$-outputs that halt and disagree at some input. Searching effectively through finite computations finds such an input, because $S$ is computable and the finite-oracle halting relation is computably enumerable. Since $B=\Phi_e^A$ is total and $A$ extends exactly one of the two successor strings, oracle-use monotonicity gives that $B$ at the witnessing input equals the value computed from the successor lying on the branch of $A$. The two successor values are unequal, so this value identifies the correct successor. This computes $Y(k)$ from $B$. Since $S$ is computable, computing all bits of $Y$ computes all finite prefixes $S(Y|n)$ and therefore computes $A$. Hence $A \leq_T B=\Phi_e^A$. Assume now that $S$ is $e$-nonsplitting and $A \in [S]$ with $B:=\Phi_e^A$ total. To compute $B(n)$ for a fixed $n \in \mathbb{N}$ without an oracle, search over all finite strings $\tau$ extending $S(\varnothing)$ inside $T$ and all computation stages until a computation $\Phi_e^\tau(n)$ halts. Such a computation is eventually found because $B(n)$ halts with some finite oracle use $u \in \mathbb{N}$; since $A \in [S] \subseteq [T]$, there is a range node $T(\gamma)$ on the branch $A$ with $u \leq |T(\gamma)|$, and the finite string $T(\gamma)$ is among the searched strings and determines the same computation. If two searches found values $m_0$ and $m_1$ from finite strings $\tau_0$ and $\tau_1$, then either the strings are compatible, in which case one extends a common finite oracle extending the other and oracle-use monotonicity gives $m_0=m_1$, or they are incompatible, in which case $m_0 \neq m_1$ would be an $e$-splitting above the stem, contradicting $e$-nonsplitting. Thus the search returns a unique value, namely $B(n)$. This gives a computable procedure for $B$. [/proof] [guided] The point of the dichotomy is to arrange that a functional below the eventual set $A$ cannot produce an intermediate noncomputable degree. There are two possible behaviours. In the splitting case, different branches of the tree force different finite outputs of $\Phi_e$, so the total output $\Phi_e^A$ contains enough information to recover which branch $A$ followed. In the nonsplitting case, all finite computations compatible with the stem agree, so any total output is independent of the oracle and is therefore computable. For the splitting case, define $B:=\Phi_e^A$ and let $Y \in 2^{\mathbb{N}}$ be the unique branch code satisfying $A=\bigcup_{n=1}^{\infty}S(Y|n)$. We compute $Y$ from $B$. Suppose that the finite string $Y|k$ has already been computed. Since $S$ is $e$-splitting, the successor strings $S((Y|k)0)$ and $S((Y|k)1)$ themselves have finite-oracle computations that halt with unequal values at some input $n$. The tree $S$ is computable and finite-oracle computations are effectively searchable, so such an input and the two halted computations can be found. The actual oracle $A$ extends exactly one of the two successor strings. Because $B=\Phi_e^A$ is total, oracle-use monotonicity gives that $B(n)$ agrees with the finite computation on the successor lying on the branch of $A$. The two finite values are unequal, so $B(n)$ determines whether $Y(k)=0$ or $Y(k)=1$. Repeating this procedure computes every bit of $Y$, and since $S$ is computable, the union $\bigcup_{n=1}^{\infty}S(Y|n)$ is computable from $Y$. Hence $A \leq_T B$. For the nonsplitting case, define again $B:=\Phi_e^A$ and assume $B$ is total. Fix an input $n \in \mathbb{N}$. We compute $B(n)$ with no oracle by searching all finite strings $\tau$ extending the stem $S(\varnothing)$ that lie inside the original computable tree $T$, in the sense fixed above: each searched $\tau$ is comparable with a range node of $T$ and compatible with a path in $[T]$. This is an effective search because the finite splitting structure of $T$ is computable. We search these $\tau$ and all finite stages until some computation $\Phi_e^\tau(n)$ halts. This search terminates because $B(n)=\Phi_e^A(n)$ halts with some finite oracle use $u \in \mathbb{N}$; since $A \in [S] \subseteq [T]$, there is a range node $T(\gamma)$ on the branch $A$ with $u \leq |T(\gamma)|$, and $T(\gamma)$ is one of the searched strings. The value found is independent of the particular finite witness. If two compatible finite oracles give halted computations on the same input, then one extends a common finite oracle extending the other, so oracle-use monotonicity gives the same value. If two incompatible finite oracles gave different values, they would be an $e$-splitting above $S(\varnothing)$, contradicting the defining nonsplitting property. Therefore the search computes exactly $B(n)$. Since $n$ was arbitrary, $B$ is computable. [/guided] [/step] [step:Construct a nested sequence of trees and diagonalizing stems] We construct, by ordinary dependent choice rather than by a uniform computable stage algorithm, computable perfect trees $(T_e)_{e \in \mathbb{N}}$ and finite binary strings $(\rho_e)_{e \in \mathbb{N}}$. Let $T_0:2^{<\mathbb{N}} \to 2^{<\mathbb{N}}$ be the identity tree $T_0(\sigma)=\sigma$, and let $\rho_0:=\varnothing$. Assume $T_e$ and $\rho_e$ have been chosen with every path through $T_e$ extending $\rho_e$. Choose a finite node $\eta_e$ inside $T_e$ properly extending $\rho_e$ that diagonalizes against $C_e$ as follows. If $C_e$ is total, choose two incompatible paths $X_0,X_1 \in [T_e]$ extending $\rho_e$; such paths exist because $T_e$ is perfect. Let $q_e \in \mathbb{N}$ be a coordinate at which their characteristic functions differ, and choose a length $\ell_e \in \mathbb{N}$ with $q_e < \ell_e$. Let $\alpha_0:=X_0|\ell_e$ and $\alpha_1:=X_1|\ell_e$, so $\alpha_0$ and $\alpha_1$ are finite strings inside $T_e$ of the same length and both values $\alpha_0(q_e)$ and $\alpha_1(q_e)$ are defined. Choose $i \in \{0,1\}$ such that $\alpha_i(q_e) \neq C_e(q_e)$, and set $\eta_e:=\alpha_i$. If $C_e$ is not total, take any proper extension of $\rho_e$ inside $T_e$ and call it $\eta_e$. This choice may depend on the truth of totality of $C_e$, but the argument only needs existence of the final set. Once the finite string $\eta_e$ has been selected, choose a range node $T_e(\gamma_e)$ extending $\eta_e$ and define the subtree $U_e:2^{<\mathbb{N}}\to2^{<\mathbb{N}}$ by $U_e(\sigma):=T_e(\gamma_e\sigma)$. Then $U_e$ is a computable perfect tree with finite parameter $\gamma_e$, every path through $U_e$ extends $\eta_e$, and every path through $U_e$ differs from $C_e$ whenever $C_e$ is total because each such path has value $\eta_e(q_e)\neq C_e(q_e)$ at the coordinate $q_e$. Apply the splitting dichotomy to the computable perfect tree $U_e$ and to the functional $\Phi_e$. The dichotomy may select one of two cases non-uniformly, but after that case and the relevant finite parameters have been fixed, the resulting object is still a computable perfect tree by the explicit searches in the proof of the dichotomy. Let the resulting computable perfect subtree be $T_{e+1}$, and let $\rho_{e+1}:=T_{e+1}(\varnothing)$ be its stem. Then $T_{e+1} \preceq T_e$, every path through $T_{e+1}$ extends $\rho_{e+1}$, the stem $\rho_{e+1}$ extends $\eta_e$, hence $\rho_e \subsetneq \rho_{e+1}$, and $T_{e+1}$ satisfies the recovery-or-computability conclusion for $\Phi_e$. [guided] At stage $e$ we have two obligations. First, we must force the eventual path not to be the $e$-th computable set if that computable set is total. Second, we must arrange that the $e$-th Turing functional cannot create an intermediate noncomputable degree below the final set. Assume $T_e$ and $\rho_e$ have already been chosen, and every path through $T_e$ extends $\rho_e$. To meet the diagonalization requirement, consider the partial computable map $C_e:\mathbb{N}\rightharpoonup\{0,1\}$. If $C_e$ is total, perfectness of $T_e$ gives two incompatible paths $X_0,X_1\in[T_e]$ extending $\rho_e$. Since the paths are incompatible, there is a coordinate $q_e\in\mathbb{N}$ at which their characteristic functions differ. Choose $\ell_e\in\mathbb{N}$ with $q_e<\ell_e$ and define finite strings $\alpha_0:=X_0|\ell_e$ and $\alpha_1:=X_1|\ell_e$. This common-length choice is important: it ensures that both $\alpha_0(q_e)$ and $\alpha_1(q_e)$ are defined. Since the two bits are different and $C_e(q_e)\in\{0,1\}$, at least one index $i\in\{0,1\}$ satisfies $\alpha_i(q_e)\neq C_e(q_e)$. Set $\eta_e:=\alpha_i$. If $C_e$ is not total, no diagonalization against a computable set is needed at this index, so choose any finite string $\eta_e$ inside $T_e$ properly extending $\rho_e$. Now convert the finite decision $\eta_e$ into a perfect subtree. Since $\eta_e$ lies inside $T_e$ and is compatible with a path through $T_e$, there is a range node $T_e(\gamma_e)$ extending $\eta_e$. Define \begin{align*} U_e:2^{<\mathbb{N}}&\to2^{<\mathbb{N}}\\ \sigma&\mapsto T_e(\gamma_e\sigma). \end{align*} The map $U_e$ is computable because $T_e$ is computable and $\gamma_e$ is a fixed finite parameter. It is perfect because it is the subtree of $T_e$ above the range node $T_e(\gamma_e)$. Every path through $U_e$ extends $\eta_e$, so if $C_e$ is total then every such path differs from $C_e$ at the coordinate $q_e$. Finally apply the splitting dichotomy to $U_e$ and $\Phi_e$. The dichotomy returns a computable perfect subtree $T_{e+1}\preceq U_e\preceq T_e$ which is either splitting or nonsplitting for $\Phi_e$. Define $\rho_{e+1}:=T_{e+1}(\varnothing)$. Since $T_{e+1}$ lies below $U_e$, every path through $T_{e+1}$ extends $\eta_e$, and hence the new stem $\rho_{e+1}$ extends $\eta_e$. Because $\eta_e$ properly extends $\rho_e$, the stems strictly increase: $\rho_e\subsetneq\rho_{e+1}$. Thus this single stage preserves nestedness, performs the diagonalization requirement for $C_e$, and installs the recovery-or-computability alternative for $\Phi_e$. [/guided] [/step] [step:Define the path and prove that it is noncomputable] Since the stems satisfy $\rho_e \subsetneq \rho_{e+1}$ for all $e \in \mathbb{N}$, define the characteristic function $a:\mathbb{N}\to\{0,1\}$ by $a(n)=\rho_e(n)$ whenever $e$ is large enough that $n<|\rho_e|$, and define the set $A \subseteq \mathbb{N}$ by $A:=\{n \in \mathbb{N}: a(n)=1\}$. The function $a$ is well-defined because the stems are nested, and we identify $A$ with its characteristic function when writing oracle computations. We verify that $A\in[T_e]$ for every $e\in\mathbb{N}$. Fix $e\in\mathbb{N}$ and a prefix length $r\in\mathbb{N}$. Choose $j\geq e$ such that $r<|\rho_j|$. Since $T_j\preceq T_e$, every path through $T_j$ is a path through $T_e$. Choose any path $X_j\in[T_j]$, which exists because $T_j$ is perfect. The path $X_j$ extends $\rho_j$, and $\rho_j|r=A|r$, so the prefix $A|r$ is extended by a path in $[T_e]$. Therefore every finite prefix of $A$ is compatible with the closed path set $[T_e]$. Since $[T_e]$ is closed in $2^{\mathbb{N}}$, it follows that $A\in[T_e]$. For each $e \in \mathbb{N}$, if $C_e$ is total, the construction chose a coordinate at which every path through $T_{e+1}$ differs from $C_e$. Since $A \in [T_{e+1}]$, we have $A \neq C_e$. Every computable subset of $\mathbb{N}$ appears as some total $C_e$, so $A$ is not computable. Therefore the Turing degree of $A$ is nonzero. [/step] [step:Show that every noncomputable degree below $A$ equals the degree of $A$] Let $B \subseteq \mathbb{N}$ be any set with $B \leq_T A$. By the definition of Turing reducibility, there is an index $e \in \mathbb{N}$ such that $B=\Phi_e^A$ and $\Phi_e^A$ is total. The tree $T_{e+1}$ was chosen to satisfy the recovery-or-computability conclusion for $\Phi_e$, and $A \in [T_{e+1}]$. If $T_{e+1}$ is in the nonsplitting case, then $B$ is computable. If $T_{e+1}$ is in the splitting case, then $A \leq_T B$. Hence every $B \leq_T A$ is either computable or satisfies $A \leq_T B$. Since $A$ is not computable, its Turing degree is nonzero. The preceding paragraph says that no nonzero Turing degree lies strictly below the degree of $A$. Therefore the Turing degree of $A$ is minimal. [/step]