Transitivity of Turing reduction

95 Views Asked by At

The Turing reduction relation is transitive meaning that if $A\leq_T B$ and $B\leq_T C$ then $A\leq_T C$. The proof I have seen for this is let $e_0$ be an index of $A$ as $B$-computable set ($A=\Phi^B_e$) and let $e_1$ be an index for $B$ as $C$-computable set. To show that $A$ is $C$ computable I simply replace in the program $e_0$ the instances in which it calls the oracle with a computation of $B$ relative to $C$ (let $d$ be the index for this program). Since this proof is rather hand-wavy I wanted to know if the index of this program depends in any way to the sets $A,B,C$ or does it only depend on $e_0$ and $e_1$. In other words let $E,F,G$ be sets such that $E=\Phi_{e_0}^F$ and $F=\Phi_{e_1}^G$ then is $E=\Phi^G_d$? I'm pretty sure that $d$ cannot be any index such that $A=\Phi^C_d$.

1

There are 1 best solutions below

3
On BEST ANSWER

It is uniform. Given $e_0$ and $e_1,$ we have $d=f(e_0,e_1)$, where $f$ is a fixed computable function. All $f$ does is look through the oracle computation $\Phi^{\_}_{e_0}$ and replace all calls to the oracle with calls to $\Phi_{e_1}^{\_}$ and return the index of that resulting oracle computation.