[proofplan] We reduce membership in $A$ to [the halting problem](/theorems/1823) relative to $A$. For each input $n$, we effectively build an oracle program which ignores its own input, asks the oracle whether $n \in A$, and halts exactly when the answer is yes. The index of this program is computable from $n$, so an oracle for $A'$ decides whether that index halts relative to $A$, which is equivalent to deciding whether $n \in A$. [/proofplan] [step:Build a uniform oracle program that halts exactly when $n$ belongs to the oracle] For each $n \in \mathbb N$, define an oracle machine scheme $M_n$ as follows. On input $m \in \mathbb N$ and oracle $X \subseteq \mathbb N$, the machine $M_n^X(m)$ queries the oracle question "$n \in X$"; if the oracle answers yes, then $M_n^X(m)$ halts, and if the oracle answers no, then $M_n^X(m)$ enters an infinite loop. Thus, for every $X \subseteq \mathbb N$ and every $m \in \mathbb N$, \begin{align*} M_n^X(m) \text{ halts} \iff n \in X. \end{align*} Because the enumeration $(\Phi_e^X)_{e \in \mathbb N}$ is acceptable, the parameter theorem for oracle machines applies (citing a result not yet in the wiki: [s-m-n theorem](/theorems/5398)). Therefore there exists a total computable map \begin{align*} p: \mathbb N &\to \mathbb N \end{align*} such that, for every $n,m \in \mathbb N$ and every oracle $X \subseteq \mathbb N$, \begin{align*} \Phi_{p(n)}^X(m) = M_n^X(m) \end{align*} in the sense of equality of partial computations. [guided] The point is to turn the question "$n \in A$" into a halting question about a program with oracle $A$. Fix $n \in \mathbb N$. We construct an oracle machine scheme $M_n$ which has $n$ hardwired into its finite code. On input $m \in \mathbb N$ and oracle $X \subseteq \mathbb N$, the machine $M_n^X(m)$ performs exactly one oracle query: it asks whether $n \in X$. If the answer is yes, it halts. If the answer is no, it repeats a fixed loop forever. Hence, for every oracle $X \subseteq \mathbb N$ and every input $m \in \mathbb N$, \begin{align*} M_n^X(m) \text{ halts} \iff n \in X. \end{align*} We also need the construction to be uniform in $n$, because a Turing reduction must compute which query to ask of the oracle $A'$. The acceptable enumeration hypothesis gives precisely this uniformity: by the parameter theorem for oracle machines (citing a result not yet in the wiki: s-m-n theorem), there is a total computable map \begin{align*} p: \mathbb N &\to \mathbb N \end{align*} such that $p(n)$ is an index for the oracle machine $M_n$. In other words, for all $n,m \in \mathbb N$ and every oracle $X \subseteq \mathbb N$, \begin{align*} \Phi_{p(n)}^X(m) = M_n^X(m) \end{align*} as partial computations. The important feature is that $p(n)$ is computable without knowing the oracle $X$; only the later execution of the program uses the oracle. [/guided] [/step] [step:Translate membership in $A$ into membership in $A'$] Now fix $A \subseteq \mathbb N$ and $n \in \mathbb N$. Applying the preceding construction with $X = A$ and $m = p(n)$ gives \begin{align*} \Phi_{p(n)}^A(p(n)) \text{ halts} &\iff M_n^A(p(n)) \text{ halts} \\ &\iff n \in A. \end{align*} By the definition of the Turing jump $A'$, \begin{align*} p(n) \in A' \iff \Phi_{p(n)}^A(p(n)) \text{ halts}. \end{align*} Combining the two equivalences yields \begin{align*} n \in A \iff p(n) \in A'. \end{align*} [/step] [step:Use the oracle for $A'$ to decide $A$] Define an oracle Turing functional $\Gamma$ as follows. On input $n \in \mathbb N$ and oracle $B \subseteq \mathbb N$, the computation $\Gamma^B(n)$ first computes $p(n)$, then queries whether $p(n) \in B$, and finally outputs $1$ if the answer is yes and outputs $0$ if the answer is no. Since $p$ is total computable and the oracle query receives a definite yes-or-no answer, $\Gamma^B(n)$ halts for every $B \subseteq \mathbb N$ and every $n \in \mathbb N$. Taking $B = A'$, the equivalence from the previous step gives \begin{align*} \Gamma^{A'}(n) = 1 &\iff p(n) \in A' \\ &\iff n \in A. \end{align*} Thus $\Gamma^{A'}$ computes the characteristic function of $A$. Therefore $A \le_T A'$, as required. [/step]