2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe one will get the class of functions Turing reducible by primitive recursive functions to the recursively enumerable sets. And determining whether that set changes when "Turing reducible by primitive recursive functions" is replaced by "Turing reducible by computable functions" or "Turing reducible by functions from the complexity class EXPTIME" is probably a nasty problem. $\endgroup$ – Thomas Klimpel Oct 13 '18 at 14:16
  • $\begingroup$ I do not understand the relationship between primitive recursive computation and limit computation that the question is trying to suggest. What's the precise question you're asking? $\endgroup$ – Carl Mummert Oct 15 '18 at 12:54
  • $\begingroup$ @CarlMummert limit computation is a well defined nice concept. The passage about "enumeration by primitive recursive functions" from wikipedia is "more dubiuous". It may be possible to formalize it in a similar way than the limit computation concept. But even if this should be possible, it remains unclear nevertheless which sort "computable class" you will get for "enumeration by ..." in the end. My precise question is exactly the question in the title: "Is enumeration by ... a useful concept?" $\endgroup$ – Thomas Klimpel Oct 15 '18 at 13:39
  • $\begingroup$ Well, enumeration by primitive recursive functions gives a more concrete characterization of the class of nonempty r.e. sets, and by functions that are not only total but very concrete (primitive recursive functions). You are right that we could limit the time bound for each input, and still have the class of nonempty r.e. sets as the class of enumeratable sets. The argument does use a special fact about primitive recursive functions, namely that the T predicate is primitive recursive. $\endgroup$ – Carl Mummert Oct 15 '18 at 13:40
  • $\begingroup$ @ThomasKlimpel I didn't really understand your question and what follows is not something I looked into detail (but a vague idea) .... so it might be wrong tbh. But here is a suggestion (I admit this is sketchy because I don't remember the precise details of the underlying concepts well enough). Here it is: If we think about the idea of minimalisation based on p.r. functions we get the general recursive functions. As I understood, your question is at least related to the question "can we use a weaker class of functions in the minimalisation process?". It seems to me that the answer may be yes. $\endgroup$ – SSequence Oct 16 '18 at 4:48
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ See math.stackexchange.com/questions/990719/… for a claimed reference that the T predicate is even polynomial time computable, and for a more elaborate proof that a class E characterized by bounded minimization, successor, addition, multiplication, less than comparison, composition, projections, and the constant function 0 contains the T predicate (and the related U predicate). $\endgroup$ – Thomas Klimpel Jun 29 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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