# I need reference proving Turing computable function with oracle of $\chi_A$ is $A$-recursive

Many introductory book for computability theory introduces turing machine with oracle and $A$-recursiveness and often assumed that they are equivalent. I can prove $A$-recursive functions are turing computable with oracle of $\chi_A$ but the other side is not that clear to me. Can I have any reference to this problem?

p.s.

set of $A$-recursive functions is the smallest set $R^A$satisfying

(i)$\chi_A$ characteristic function of $A$, zero function, projection function$\in R^A$

(ii)closed under primitive recursion

(iii)closed under composition

(iv)closed under $\mu$-operator(minimisation)

Turing machine with oracle of $\chi_A$ is composed of two tapes, working tape and oracle tape. first one is just like ordinary turing machine tape, and on the second one the value of $\chi_A$ is written$($$\chi_A(0),\chi_A(1),...$)

• Could you please provide the definitions you use? I would consider those terms to be synonyms. – hmakholm left over Monica May 13 '18 at 11:32

One simply relativizes the usual proof that the Turing computable functions are precisely the same as the recursive functions.

The direction that you need is to prove that the Turing A-computable functions are contained within the class of A-recursive functions. There are many details, but let me sketch the argument.

What you need to do is to show that with $A$-recursive functions, we can simulate Turing machines. So you need to arithmetize the operation of Turing machines with oracle $A$, which means to develop an encoding of Turing machines using numbers.

So we develop a concept of a "snapshot" of an $A$-Turing machine computation, which is a list of information completely describing the state of the machine: the program, the head position and the contents of the (work) tape. We don't need to encode the information of the oracle $A$ into the snapshot, since this encoding presumes that it is $A$ that will appear on the oracle tape.

Next, we prove that the basic computable operations on these snapshots are $A$-recursive. That is, the function $\text{OneStep}(s)=t$, which takes a shapshot $s$ and outputs the snapshot $t$ of what the computation would achieve after one step of computation. This will use $\xi_A$, since the machine program might have consulted the oracle during this step.

Ultimately, we'll be able to show that the function $f$, which has $f(x)=y$ when there is a sequence of snapshots $s_0, s_1,\ldots,s_n$, where $s_0$ is the starting snapshot of a certain program $p$ on input $x$ and each $s_{i+1}=\text{OneStep}(s_i)$, and $s_n$ is a snapshot of a halted computation showing output $y$. You will use the $\mu$-operator in this part of the argument, to get the least number coding the sequence of snapshots, if there is such a sequence.

The point is that there will be such a sequence of snapshots just in case the function computed by program $p$ on input $x$ really does give output $y$. One can prove inductively that the simulated computations agree with the actual computations.

Thus, every Turing $A$-computable function is $A$-recursive.