# Primitive Recursion equipped with an evaluator function

The wikipedia article for primitive recursion mentions a limitation that primitive recursive function can't compute the function $ev(i,j)$ which computes the $i$th primitive recursive function on input $j$.

I was wondering what you can compute with primitive recursion equipped with $ev$, which I will refer to as secondary recursive functions.

More formally,

• any primitive recursive function is secondary recursive
• secondary recursive functions are closed under composition and primitive recursion (just like primitive recursive functions)
• $ev$ is secondary recursive
• $ev$ indexes function such that computing the index of a projection, composition, or recursion is primitive recursive.

Note that in the above, $ev$ is still only computing primitive recursion. Thus, secondary recursion always halts - $ev$ always halts and the other ways of building secondary recursive functions can't turn halting functions into non-halting functions.

I've found that some "nice" examples of non-primitive-recursive functions are secondary recursive.

For example, for any fixed $n$ , the function $f_n(a,b) = a \uparrow^n b$ is primitive recursive. Given arbitrary $n$, we can compute the index of $f_n$ (with some work), then use $ev$ to compute $arrow(a,b,n) = a \uparrow^n b$ which is not primitive recursive (it can be used to compute the Ackermann function).

We can also further generalize this to $n$-ary recursion, with $1$-ary recursion being primitive recursion, and $(n+1)$-ary recursion being primitive recursion equipped with an function that evaluates $n$-ary recursive functions. (Then we can generalize this even further, with $\omega$-ary recursive functions which are the union of $n$-ary recursive functions for all $n$, $(\omega+1)$-ary recursion being primitive recursion equipped with a function that evaluates $\omega$-ary recursion etc. )

I have 2 questions:

• Have these been studied? Do they have a name?

• Are there any "nice" examples of functions which are recursive but not secondary recursive?

• Regarding your second question, have you tried diagonalization? – Yuval Filmus May 22 '16 at 21:48
• @YuvalFilmus Yes, the function $ev_2(i,j)$ which evaluates the $i$th secondary recursive function on input $j$ is not secondary recursive. But by "nice" functions I mean functions that don't involve the definition of secondary recursion. – cardobard_box May 22 '16 at 21:55