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.

  • $\begingroup$ To clarify, by that property for PR(f) I guess you mean: if a computable function is computable in time bounded by a function in PR(f), then it is itself in PR(f). $\endgroup$ Jan 9, 2018 at 11:45
  • $\begingroup$ @JoelDavidHamkins Yes, exactly. $\endgroup$
    – user39297
    Jan 9, 2018 at 11:46

1 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.

  • $\begingroup$ Thank you. It seems I had the same line of thought, but got lost in details. It seems the proof would also go through with elementary functions in place of primitive recursive functions, which makes my life easier :) $\endgroup$
    – user39297
    Jan 9, 2018 at 12:41
  • $\begingroup$ The argument seems to show that any class of functions that is closed under primitive recursion and composition and contains the PR-basic functions will be closed under bounded search, and therefore will have your property. You can start with any family of functions and close under primitive recursion and composition (and more, if you like), and you'll get the property. $\endgroup$ Jan 9, 2018 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy