It is an important theorem that the recursive functions are exactly those which are definable by $\Delta^0_1$ formulas.
We have just finished the part about incompleteness in a course I'm TA'ing, and a student has asked me the following question, and I had no idea how to answer it properly. I'll slightly refine the question.
We know that the recursive functions are built from the basic functions by closing them under schemata of composition, primitive recursion and minimization. We know that it's not enough to describe functions which are $\Sigma^0_1$ or $\Pi^0_1$, or even higher up the arithmetical hierarchy.
- Are there other schemata which allow us to reach higher up the hierarchy?
- Can we control just how far we are reaching into the hierarchy?
- And are there any schemata which allow us to define all the predicates in the hierarchy?
One kind of schemata that would let us move up the hierarchy would be "appeal to an oracle." The idea is that in addition to building up functions from basic functions by composition, primitive recursion, and $\mu$-recursion, we also allow in our construction of functions appeal to finite initial segments of a specified function $f$, which we call an "oracle." Here, $f$ could be any function we like, so long as we fix a particular $f$ before our construction. For instance, $f$ could be the characteristic function of a $\Sigma_n^0$ set, or it could be a function that computes the halting problem (in a non-recursive way). In any case, if we allow appeals to this oracle, and we construct a function $g$ in this way, we say that $g$ is recusrive in $f$, or $f$-recursive. This is one easy way to control your movement up the hierarchy. If your oracle $f$ is $\Sigma_n^0$, then your function $g$ is at best $\Sigma_n^0$.
You can even ascend higher into the "analytic" hierarchy, if you allow yourself usage of function quantifiers (which requires second-order logic). These reside even higher up than any of the classifications in the arithmetic hierarchy.