Primitive Recursion equipped with an evaluator function

Question

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?

• Yuval Filmus: Regarding your second question, have you tried diagonalization?
• cardobard_box: @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.

Answer 1

A paper of Sylvain Schmitz, Complexity hierarchies beyond elementary, seems to tackle a similar question. While not necessarily defining your exact class (I haven't read the paper), it discusses classes of function between primitive recursive and recursive (as well as between elementary and primitive recursive).