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?
