What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?

Question

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 Gödel'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 Gödel's recursive functions ("Gödel 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:

Problem

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 Gödel complexity of that function.

Answer 1

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

Answer 2

Your problem is related to the issue of defining meaningful measures for time- and space complexity for $\lambda$-calculus. Recently there has been a breakthrough: Accattoli and Dal Lago show in their paper Beta Reduction is Invariant, Indeed that, simplifying a bit, if you count the number of reduction steps of a $\lambda$-term, you get a measure of time-complexity that agrees with the standard classes (e.g. P, NP, EXP, ...) defined using Turing machines.

Answer 3

Unless I misunderstand something:

• The best-case representation for $g(x) = x+1$ as a primitive recursive function takes time $1$, if we agree that each "call" to the primitive successor function requires one algorithmic step. This is trivial: computing $g(x)$ always requires exactly one invocation of the primitive successor function.

• Common Turing machine models (such as those that require $O(|x|)$ steps to compute $x-1$, as in the question) will not be able to compute $g(x) = x+1$ in a bounded amount of time.

The same holds for computing $f(x) = x-1$. The usual primitive recursive definition of this function uses no successor operations at all, and runs in constant time if we define the projection functions to use short-circuit evaluation by not evaluating the arguments that they don't return. The definition is given by recursion as $f(0) = 0$ and $f(x+1) = \pi^2_1(f(x),x)$.

So the goal of the question cannot be achieved, under the Turing machine conventions in the question, but not for the reason suggested.

This is a key point about what happens if we try to capture the complexity of a primitive recursive function by counting function invocations. The successor operation can add 1 to any number in one "step", regardless of the size of the number; the primitive recursion combinator can, in one "step", determine whether a given number $z$ is 0, and also compute $z-1$ if $z$ is positive.