Is enumeration by primitive recursive functions a useful concept?

349 Views Asked by At

The wikipedia article on the complexity class of all primitive recursive functions says

..., we can "enumerate" any recursively enumerable set (...) by a primitive-recursive function in the following sense: given an input (M, k), where M is a Turing machine and k is an integer, if M halts within k steps then output M; otherwise output nothing. Then the union of the outputs, over all possible inputs (M, k), is exactly the set of M that halt.

I have the feeling that this argument uses no special properties of primitive-recursive functions, and should work just as well for elementary recursive functions or even function from the complexity class EXPTIME. After all, if k is encoded in binary, then the runtime of the described function taking (M,k) as input is at most exponential in the length of its input.

So why do I even ask, if this concept seems so obviously misguided? Of course I might be missing something, but that is not my reason. My reason is that the concept of computation in the limit does make sense to me, but I cannot clearly pin down the point were it really deviates from the above concept. The proofs do use that limit computability is preserved by Turing reduction, and this seems to be absent for the above concept. In the end, the above concept might really yield exactly the recursively enumerable sets, which itself is of course a useful concept.

1

There are 1 best solutions below

1
On

The confusing passage in the wikipedia article is actually an out of context quote from the Complexity Zoo entry on PR: Primitive Recursive Functions:

An interesting difference is that PR functions can be explicitly enumerated, whereas functions in R cannot be (since otherwise the halting problem would be decidable). In this sense, PR is a "syntactic" class whereas R is "semantic."

On the other hand, we can "enumerate" any ...

So the original intention of the passage was not to introduce that strange concept of enumeration by primitive recursive functions, but to explain that "PR functions can be explicitly enumerated", that computable total functions cannot, but that any recursively enumerable set can. (It fails, but the point itself is appropriate.)


However, the question worried less about whether the concept of enumeration by primitive recursive functions makes sense, but about how it differs from the concept of computation in the limit. Both get in a natural number, and the final result is determined by observing the results as the number increases.

Using a natural number $s$ in this way allows to define various operators, like a finally-constant-value operator or a finally-constant-after operator, which can make computation in the limit more concrete. It also allows to define the well-known μ-operator, minimization operator, or unbounded search operator in a way that it can be used "inside" the class of primitive recursive functions.

The μ-operator could be defined in terms of the bounded μ-operator $$\mu y_{y<z} R(y). \ \ \mbox{The least} \ y<z \ \mbox{such that} \ R(y), \ \mbox{if} \ (\exists y)_{y<z} R(y); \ \mbox{otherwise}, \ z$$ as $\mu y R(y) := \mu y_{y<s} R(y)$. The finally-constant-value operator could be defined as $\operatorname{fcv}yf(y):=f(s)$ and the finally-constant-after operator could be defined as $$\operatorname{fca}yf(y). \ \ \mbox{The least} \ y\leq s \ \mbox{such that} \ \forall x\in[y,s] f(x)=f(y).$$

As $s$ goes to infinity, eventually those operators will compute the correct value. So where is the crucial difference between those operators, which makes the μ-operator well accepted (and well-known) while the other two operators are uncomputable (and never-heard-of)? The difference is that the result of the μ-operator can be checked for correctness by a primitive recursive function, but the result of the other two operators cannot. For the finally-constant-after operator, one could at least try to check a bit by using a primitive recursive function to define a range over which one checks that $f(y)$ is constant.

(The finally-constant-value operator $\operatorname{fcv}$ and the finally-constant-after operator $\operatorname{fca}$ have the same strength over a sufficiently strong class of functions. $\operatorname{fcv}yf(y)=f(\operatorname{fca}yf(y))$ shows that $\operatorname{fca}$ is at least as strong as $\operatorname{fcv}$. For the other direction, assume that the class of functions allows to define a last-changed-at operator $g:=\operatorname{lca}yf(y))$ such that $g$ satisfies $g(0)=0$, $g(n+1)=g(n)$ if $f(n+1)=f(n)$ and $g(n+1)=n+1$ otherwise. Then $\operatorname{fca}yf(y)=\operatorname{fcv}y(\operatorname{lca}zf(z))(y)$, which shows that $\operatorname{fcv}$ plus $\operatorname{lca}$ are at least as strong as $\operatorname{fca}$.)

From this perspective, using the union operator as a mean to "determine the final result by observing the results" is harmless. But allowing functions Turing reducible by primitive recursive functions to that specific enumerated set would not be harmless. (The stated intention of the original source was to "enumerate any RE set by a PR function", which should be possible, even so the given construction was insufficient, since it just enumerated one specific RE set.)


There was also the discussion whether any special properties of primitive recursive functions is used in any of the concepts discussed here. A good answer is probably Carl Mummert's remark that the primitive recursive functions are a very concrete set of computable total functions. Any justifications beyond that like the remark that "the T predicate is primitive recursive" miss the point of the discussion, since the T predicate is also elementary, i.e. does not need the full strength of the primitive recursive functions.

This also applies to the μ-operator. It is sufficient to have successor, addition, multiplication, less than comparison, composition, projections, and the constant function 0, to get the entire set of partial computable functions if the μ-operator is available. No need for primitive recursion (or even the power function).