A constructive algorithm for a jump of a low set. Suppose we have an oracle Turing machine which, with $K$ (the halting problem) as an oracle, computes a low set $A$. ($A$ is low if $A'\equiv_T K$)
Is there an algorithmic way of obtaining a Turing machine which with $K$ as an oracle compute $A'$ -- the jump of $A$?
To be speciffic. Is there a Turing machine (which uses $K$ as an oracle) which for every proper input (a code of an oracle Turing machine which, with $K$ as an oracle, computes a low set) outputs a code of an oracle Turing machine which, with $K$ as an oracle, coputes the halting problem for $A$?
It is easy to see that an oracle Turing machine which, with $K'$ as an oracle, solves this task. But is there one which uses only $K$?
 A: I think the answer is no. There might be a simpler argument than the one I'm going to expose now. I first give some notations:


*

*$\Phi^X_e(n)$ is the result of the algorithm coded by $e$ on input $n$ and using $X$ as an oracle.

*$\Phi^X_{e,t}(n)$ is the result of the algorithm coded by $e$ on input $n$ and using $X$ as an oracle, at stage $t$ of computation. If the value $\Phi^X_{e,t}(n)$ is undefined for every $t$ then $\Phi^X_e(n)$ is undefined (the algorithm does not halt). If $\Phi^X_{e,t}(n)$ is defined for some $t$, the we assume that for every $t'\geq t$ we have $\Phi^X_{e,t}(n) = \Phi^X_{e,t'}(n) = \Phi^X_e(n)$.

*If $\Phi^X_e(n)$ is defined for every $n$ and equal to $0$ or $1$, then $\Phi^X_e$ denotes the corresponding subset of $\omega$.

*If $\Phi^X_e(e)$ halts then $X'(e)=1$. If $\Phi^X_e(e)$ does not halts then $X'(e)=0$.
We should prove that there is no total computable function $f$ such that if $\Phi^K_e$ is a low set $A$, then $\Phi^K_{f(e)}$ is $A'$. 
We will even prove something stronger : There is no total computable function $f$ such that if $\Phi^K_e$ is a computable set $A$, then $\Phi^K_{f(e)}$ is $A'$. 
This might seems wrong at first, as we clearly have a total computable function $f$ such that if $\Phi_e$ is a computable set $A$, then $\Phi^K_{f(e)}$ is $A'$. So in particular, what it says is that if $\Phi^K_e$ is computable, then there is no uniform way to compute a code $a$ so that $\Phi^K_e=\Phi_a$. In other words, $K$ is not needed for the computation, but we don't know how to create a new computation without $K$, just based on the algorithm that uses $K$.
Also note that it is harmless to suppose $f$ computable and total instead of just $K$-computable and partial. Indeed, suppose that $f'$ is a partial $K$-computable function that transform algorithms using $K$ to other algorithms using $K$. Then we can build $f$, by saying that $f(e)$ halts and return a code for an algorithm that wait for $f'(e)$ to halt before doing anything, and which then does what $f'(e)$ would do.
Let us now do the proof:
So let us suppose for contradiction, that there is a total computable function $f:\omega \mapsto \omega$, such that if $\Phi^K_e$ is a computable set $A$, then $\Phi^K_{f(e)}$ is $A'$. 
The strategy is as follow: We will build a total computable function $g:\omega \mapsto \omega$, such that: 


*

*For any $e$, either $\Phi^K_{f(e)}$ is not a set (the function of code $f(e)$ is not total with $K$ as an oracle), or $(\Phi^K_{g(e)})' \neq \Phi^K_{f(e)}$.

*For any $e$, we have that $\Phi^K_{g(e)}$ is a computable set.
Then by the Kleene fixed point theorem, there is a code $a$ so that $\Phi^K_{g(a)}=\Phi^K_{a}$. As $\Phi_{g(e)}$ is always a computable set for any $e$, then also $\Phi^K_{a}$ is a computable set $A$. But then we have $A' = (\Phi^K_{g(a)})' \neq \Phi^K_{f(a)} = A'$ which is a contradiction.
Now how to build $g$ ? Let us fix a code $b$ such that $\Phi^X_b(b)$ halts iff $X(n)=0$ for some $n$, and which does not halt if $X(n)=1$ for every $n$.
Now we define $g$ to be the function, such that 


*

*$\Phi^K_{g(e)}(t) = 1$ if $\Phi^K_{f(e), t}(b)$ does not halt

*$\Phi^K_{g(e)}(t) = 1$ if $\Phi^K_{f(e), t}(b)$ halts and is $1$

*$\Phi^K_{g(e)}(t) = 0$ if $\Phi^K_{f(e), t}(b)$ halts and is $0$


For any $e$, the set $\Phi^K_{g(e)}$ is clearly computable because it is either everything (= $\omega$), or finite (with only finitely many 1). Now suppose that $\Phi^K_{f(e), t}(b)$ halts from some $t$ and is equal to $1$. Then $\Phi^K_{g(e)}(t)$ is everything and by definition of $b$, the value of its jump at position $b$ should be $0$ (corresponding to 'does not halt'). Also if $\Phi^K_{f(e), t}(b)$ halts from some $t$ and is equal to $0$, then by definition of $b$ , the value of its jump at position $b$ should be $1$ (corresponding to 'halt').
Therefore we have $(\Phi^K_{g(e)})' \neq \Phi^K_{f(e)}$ and this conclude the proof.
