Talk:PR (complexity)

Functions that can be explicitely enumerated

In Primitive_recursive_function, it is said that:
the partial computable functions [...] can be explicitly enumerated
while in this article, I can read:
PR functions can be explicitly enumerated, whereas not all functions R can be.
I think that the first affirmation is correct, while the second displays poor grammar, so that I can't be sure whether I understand the sentence correctly or not. Anybody with more self-confidence can correct ? --Gzorg (talk) 14:43, 27 May 2013 (UTC)

• Answering to myself: R is the set of total recursive functions. Noted. --Gzorg (talk) 14:49, 27 May 2013 (UTC)

Although correct I agree that the sentence is confusing. It is correct because, to enumerate the recursive functions, one needs an algorithm to test if a function eventually halts on every input. As Cantor's diagonal argument shows that an algorithm cannot exits which tests if a function halts on a given input, this is impossible.

By the way, this article is very badly written. Many important facts are omitted or not clearly stated. Namely: A recursive function is a function that may be programmed by most computer languages. A PR function is a function that uses only loops for which the number of iterations may be bounded when entering the loop (otherwise, general while loops are forbidden, while for i from 1 to n loops are allowed, possibly with exit allowing premature end of the loop). Theorem: A recursive function is primitive recursive if and only if the number of steps of its execution on an input of size n is bounded by a primitive function of n. This latter theorem may be interpreted by saying that a non-primitive recursive function does not have any better complexity measure than running it and see how long it takes. D.Lazard (talk) 15:41, 27 May 2013 (UTC)

Most of the info should be in Primitive recursive function. These "Foo (complexity)" pages are all very short. Compare Computable function and R (complexity). — Carl (CBM · talk) 18:13, 3 June 2013 (UTC)

There's another issue here. The Turing machine programs that generate PR functions can be enumerated and the programs that generate R functions cannot. But that's not the same thing as enumerating the functions themselves because each ffunction may be represented as multiple different programs and it's not possible to enumerate them in a way that produces only one program per function (because it's undecidable whether two programs represent the same function). —David Eppstein (talk) 15:52, 27 May 2013 (UTC)

Yes, this is a completely bungled sentence: "PR functions can be explicitly enumerated, whereas not all functions R can be. This shows that PR has a syntactic definition, whereas R lacks one.". Here is what it does not mean:

1. That there is some recursive function that cannot be enumerated (i.e. its graph is not r.e.). In general a function is (partial) computable if and only if its graph is r.e.
2. That the set of indices of primitive recursive function *can* be enumerated. That is impossible, by Rice's theorem.

What the sentence is most likely trying to say is that:

• There is a computable function $U(e,n)$ such that
  1. For every $e$, $\lambda n. U(e,n)$ is primitive recursive
  2. For every primitive recursive unary $f(n)$ there is an $e$ such that $f = \lambda n. U(e,n)$. We can even assume $e$ is unique, in this case.

This is the usual sense in which a sequence of functions is enumerated, but it is not what a naive reader is likely to take away from the sentence. I am just going to remove it. — Carl (CBM · talk) 17:18, 3 June 2013 (UTC)

Redundant article?

There is a much longer article on Primitive recursive functions. This article adds very little of substance, if at all, and at any rate describes precisely the same concept. It is unhelpful to have two articles on the same concept. AmirOnWiki (talk) 12:00, 3 October 2013 (UTC)