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?


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),...$)

  • $\begingroup$ Could you please provide the definitions you use? I would consider those terms to be synonyms. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.