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:

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

2more comments