6
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ Jun 19, 2013 at 1:41
  • 5
    $\begingroup$ 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. $\endgroup$ Jun 19, 2013 at 2:03
  • $\begingroup$ 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). $\endgroup$
    – user21816
    Jun 19, 2013 at 2:05
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 19, 2013 at 2:17
  • 2
    $\begingroup$ 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. $\endgroup$
    – usul
    Jun 19, 2013 at 3:12

3 Answers 3

8
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 19, 2013 at 18:46
  • $\begingroup$ @Dan Turetsky: as I point out in my answer, the question is somewhat trivially unsolvable in that context. $\endgroup$ May 5, 2014 at 18:39
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ I think there are reasonable TM models where $x\mapsto x+1$ is computable in constant time. For example, if we use unary notation on a bi-infinite tape, with the convention that the head sits on the end of the input string, then all we have to do is add one more $1$ and halt, which takes constant time. $\endgroup$ May 5, 2014 at 22:10
  • $\begingroup$ @Joel: Silly Turing machines - everyone has their own idea how they work! In my mind they need to start on the first symbol of input. This is also (likely) why the author said that $h(x) = x-1$ takes $O(|x|)$ steps; it would also take only one step if the machine started on the last digit. I'll edit the answer, however. $\endgroup$ May 5, 2014 at 22:13
  • $\begingroup$ @Joel: By the way, there is a technical reason to start the machine on the first input symbol, which is to accommodate machines that have a one-sided (i.e. semi-infinite) input tape, which are common in the computational complexity literature. These need to know where the left end of the tape is, because in the usual framework they have no way to find it otherwise. $\endgroup$ May 5, 2014 at 22:55
  • $\begingroup$ It’s clear from the first example in the question that they meant numbers to be written in binary. $\endgroup$ May 5, 2014 at 23:09
  • $\begingroup$ @CarlMummert Oh, I agree that there are a variety of TM models. In some of the semi-infinite models, one can check the left-most cell condition, if they operate according to the rule that moving left from that cell simply causes no movement (but the program continues anyway). In this model, one can institute a left-cell check, by means of writing some string (e.g. 10), and then moving left and then checking if it is still there in the expected place. If not, you're on the left-most cell. But in other models, moving left from the left-most cell causes computation to stop. $\endgroup$ May 5, 2014 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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