Skip to main content
added 512 characters in body
Source Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

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.

  • There is no reasonableCommon Turing machine modelmodels (such as those that require $O(|x|)$ steps to compute $x-1$, as in which the timequestion) will not be able to compute $g(x) = x+1$ is constantin 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.

Unless I misunderstand something:

  • The best-case representation for $g(x) = x+1$ as a primitive recursive function takes time $1$, if 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.

  • There is no reasonable Turing machine model in which the time to compute $g(x) = x+1$ is constant.

So the goal of the question cannot be achieved, 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.

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.

Source Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68

Unless I misunderstand something:

  • The best-case representation for $g(x) = x+1$ as a primitive recursive function takes time $1$, if 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.

  • There is no reasonable Turing machine model in which the time to compute $g(x) = x+1$ is constant.

So the goal of the question cannot be achieved, 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.