Assume we have
computable f so that
φeA(0)↓⟺φf(e)B(0)↓. Want to find a computation for
A from
B.
So say we have
B as an oracle, and take input
n∈N. Need to tell if
n∈A. Create the oracle programs
e,e∗ given by
φeO(k)={1loopn∈On∈/Oand
φe∗O(k)={loop1n∈On∈/O
so that
n∈Aby construction⟺φeA(0)↓by f⟺φf(e)B(0)↓and
n∈/Aby construction⟺φe∗A(0)↓by f⟺φf(e∗)B(0)↓
Now dovetail the programs
f(e),f(e∗) to produce a new program
φd which
relative to an oracle
O and on any input
k executes
φf(e)O(k) and
φf(e∗)O(k) in parallel, halting with
1 if the former program halts and halting with
0 if the latter program halts. (This is ill-
defined on inputs for which both computations might halt, since we don’t specify which output to prefer. This will not happen in our use-case, though.)
Choose
O=A and
k=0 and consider the computation
φdB(0). This will halt with
1 iff φf(e)B(0) halts, which by construction occurs
exactly when n∈A; likewise,
φdB(0) will halt with
0 iff φf(e∗)B(0) halts, which by construction occurs
exactly when n∈/A. Also, exactly one of these two programs will halt since exactly one of
n∈A and
n∈/A are true; therefore,
φdB(0) is both well-
defined and total.
Since we’ve taken
B as an oracle, we can now just execute
φdB(0), wait for it to halt, observe its output, and then appropriately conclude either
n∈A or
n∈/A.