A "dense" extension of the set of primitive recursive functions

Question

Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make this a true extension, assume $f$ outgrows all primitive recursive functions.

Now, $\mathcal{PR}$ is "dense" in the sense that it has the Ritchie-Cobham property, i.e. every function computable in primitive recursive time is primitive recursive and vice versa.

Does $\mathcal{PR}(f)$ have the Ritchie-Cobham property?

To me it seems natural the extension preserves the property and I would guess there is some "direct" argument for this, which I just fail to see.

Answer 1

The answer is yes.

Suppose a function $g$ is computable by a procedure $p$ whose computation running time is bounded by a function $h\in\newcommand\PR{\text{PR}}\PR(f)$. I claim that $g\in\PR(f)$.

To see this, let's first argue that $\PR(f)$ is closed under the bounded search operator $(x,z)\mapsto\mu y<z[R(x,y,z)]$, where $R$ is a relation whose characteristic function is in $\PR(f)$ and where the $\mu$ operator returns the least $y<z$ such that $R(x,y,z)$, if there is one, and otherwise returns $z$ as a signal that the search failed. The proof is just the usual proof that the primitive recursive functions are closed under bounded search, since one can easily define this instance of the $\mu$ operator by recursion, by using $R$. In other words, the usual argument is not sensitive to the particular functions one starts with in the $\PR$ hierarchy.

It follows now that $g$ is in $\PR(f)$, since we can say that $g(x)=y$ just in case there is a code for a computation of length $h(x)$ showing that the output of $g$ on $x$ is $y$ according to the fixed program $p$. This code can be checked using bounded search, since we can bound how big the code will be if we know how long the computation will be.