Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let me begin with an example.

Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, and return. However, the "best" definition of $f(x) = 2x$ built from the Godel's primitive recursive functions will use primitive recursion to take $x$ successors of $x$ and return the result. If we intuitively hold that each "call" to the primitive successor function requires one algorithmic step, then the function $f(x) = 2x$ requires $O(2^{|n|})$ steps.

From this example, we can see that the intuitive notion of time complexity associated with Turing machine computation ("Turing complexity") and the intuitive notion of time complexity associated with Godel's recursive functions ("Godel complexity") do not coincide. My goal is to tweak the definition of the recursive functions to make it so these concepts do coincide.

One attempt is to add $f(x) = 2x$ to the list of primitive recursive functions. But there are still problems: for example, the function $f(x) = x - 1$ is still $O(|n|)$ on a Turing machine, but $O(2^{|n|})$ when expressed as the combination of primitive recursive functions.

This is my question:


Find a set of new primitive recursive functions that can be added to the original three primitive recursive functions such that the best-case Turing complexity of any computable function is always equal to the best-case Godel complexity of that function.

share|improve this question
By "equal to," do you mean "equal to (modulo a constant factor)"? Also, I presume that by "best-case" you mean "optimal worst-case;" is that right? –  Noah S Jun 19 '13 at 1:41
You seem to be using binary notation in your Turing computation, and the phenomenon of your example arises purely in the Turing context, when one compares Turing-machines with unary notation versus Turing machines with binary notation. The Turing time to compute $2x$ in unary notation is about the same as what you are calling the Goedel time for computing $2x$. Could you clarify your set-up more precisely? After all, Turing machines operate with finite strings, and primitive recursive functions (ordinarily) operate with natural numbers. –  Joel David Hamkins Jun 19 '13 at 2:03
Yes, by "best-case" I mean "optimal worst-case," thank you. By "equal to," I mean "asymptotically equal to" - I would like it such that (for example) if a function can be implemented in $O(|n|)$ time on a Turing machine, then it can necessarily be implemented in $O(|n|)$ time via primitive recursive functions (and vice versa). –  user21816 Jun 19 '13 at 2:05
My point was that you were assuming a particular notation in the Turing machines, since in unary notation (where we represent $n$ by $n$ many $1$s), you can't just add a $0$ to the end as you said; instead, you have to double the number of $1$s appearing on the tape, which takes about the same time as doing the primitive recursive recursion. –  Joel David Hamkins Jun 19 '13 at 2:17
This kind of issue may be one reason that we relax the notion of "efficient" to "polynomial-time computable"; it seems to generally be nicely model-independent. –  usul Jun 19 '13 at 3:12
show 1 more comment

1 Answer

Since there are computable total functions that are not primitive recursive, one cannot make the two notions of time complexity coincide. If we add any primitive recursive function as an initial function in the primitive recursive hierarchy, the resulting hierarchy will still consist entirely of primitive recursive functions. And so we may take any computable total function that is not primitive recursive, and this function can have no "recursive definition" as a primitive recursive function and thus has no Gödel complexity.

Furthermore, if one entertains the idea of addressing this issue by adding a computable function $g$ that is not primitive recursive, and building the primitive recursive hierarchy on top of that function, then again it will not succeed, since the class of computable total functions is not the same as those that are primitive recursive relative to any fixed computable total function $g$. One can prove this by observing that we have a computable function that is universal for all such functions, simply by unwrapping the primitive recursive definitions and evaluating them. And so by diagonalization there will be a computable total function that is different from any function obtainable by performing primitive recursion over $g$.

share|improve this answer
We can make the question meaningful by asking it for primitive recursive functions instead of all recursive functions. I think it's an interesting question then. –  Dan Turetsky Jun 19 '13 at 18:46
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.