Talk:Primitive recursive function
 | Mathematics B‑class Mid‑priority | |||||||||
| ||||||||||
Old comments
Comments on previous changes:
- the initial set of X: they are axioms, not functions or terms. they are statements.
- successor: you had better not use + in the definition. we haven't defined addition.
- projection: the s suffix on words makes things plural.
- p.r. versus primitive recursive: I personally think it was nicer with the abbreviation, but it's not a strong opinion.
I spent a lot of time in crafting this page. Please do me the courtesty of investing a similar degree of effort in your changes. --Wmorgan
Regarding number 2: I was assuming knowledge of the natural numbers and their addition. If you want to assume only Peano's axioms and start everything from there, you should link to the Peano axioms and not to "natural number line". Or do you want to start from a primitive, "geometric" understanding of the natural number line? --AxelBoldt
I think you have a point that "natural number line" does presuppose some ideas which I shouldn't assume are defined at this point. But certainly as addition is defined later on in the page I think it would be safest not to use it explicitly quite yet. Actually I'm a bit unclear as to whether the Peano postulates should be assumed or not. The textbook that I have on this subject (Epstein & Carnelli) uses the phrase "that number which follows n in the natural number series". Thoughts?
(BTW in rereading my comments above I come off as fairly obnoxious. That wasn't my intention, so please accept my apologies.)
And one last comment... I think I will change the definition of the set of p.r. functions to an inductive one rather than using terms like "smallest" and "closed", as upon further study, the latter, taken in the set-theoretic sense, presupposes infinite classes of functions, whereas with the former we can stay safely away from the i- word. --Wmorgan
You need at least the Peano axioms; otherwise you cannot talk about natural numbers in any meaningful way. I would probably not even bother; just mention the natural numbers, link to them, and be done with it. Then later show that the "intuitive addition" of natural numbers can be defined as a p.r. function. Everybody knows the natural numbers (or they think they do).
Also, a nice example of a p.r. function would be f(x,y) = 1 if x < y and 0 if x ≥ y. And maybe a typical function that's recursive but not p.r. --AxelBoldt
Diagonal argument
- [about the diagonal argument:] Note that this argument can be applied to any class of functions that can be enumerated in this way. (One might think this implies that any explicit list of the computable functions cannot be complete, but that's false because of the undecidability of the Halting Problem.)
(One might think this implies that any explicit list of the computable functions cannot be complete, but that's false because of the undecidability? of the Halting Problem.)
I changed this back, clarifying that we only talk about total computable functions here. Indeed, an explicit (in the sense of recursively enumerable) list of total computable functions can never be complete, as the diagonal argument shows.
It is possible to have a complete explicit list of partial computable functions though. I guess that's the misunderstanding. 199.17.234.96
I don't understand what the point of this 'diagonal argument' is. To show that there are computable functions that are not Primitive Recursive one just exhibits one -- such as Ackermann (as is written at the end of the article). Does anyone have an the objection to snipping this bit out? --Sam Staton 15:56, 23 May 2006 (UTC)
Gödel's incompleteness theorem
An essential piece of Gödel's theorem uses primitive recursive functions...should that be noted here?
Sentence structure
- Many of the functions normally studied in number theory, and approximations to real-valued functions, are primitive recursive, such as addition, division, factorial, exponential, finding the nth prime, and so on (Brainerd and Landweber, 1974).
It hurts to read this sentence. Fredrik Johansson 00:53, 30 April 2006 (UTC)
- Fixed, I think. Adam (talk) 04:02, 23 October 2008 (UTC)
Zero-based or One-based numbering?
Whoever is in charge of this article should make up his/her mind whether he/she is using zero-based numbering or one-based numbering for lists of functions and for their arguments. JRSpriggs 03:14, 30 July 2006 (UTC)
- Since no one else did anything, I converted the article to consistent one-based numbering. Please let us keep it that way. JRSpriggs 03:57, 3 August 2006 (UTC)
ideas to improve the article
Hi. I made a comment on the math Wikiproject talk page that this article needed some improvement. An editor has asked me to give more precise comments so here goes.
- My main criticism is that the page is not readable enough for the layman. Of course, this is not a really easy subject but still, I think the intro for one should say a bit more. For instance giving a quick definition of a computable function and some basic intuition as to why anyone would consider primitive recursive functions in the first place.
- There's not enough discussion as to why these were considered.
- point 2 of the definition should be restated in a cleaner way.
- again, following the definition, there should be an attempt at conveying some intution, enough so that people would accept the proof that addition is primitive recursive without involving the projections.
- the limitations section begins by saying that primitive recursive correspond to our intuitive notion of computable. In the computer age, I think that's pretty much incorrect.
The article is not that bad, but it could need some help if one wants to rely on it for other articles, notably the Ackermann function. Pascal.Tesson 19:31, 18 September 2006 (UTC)
- Since your criticisms are not entirely clear to me, I suggest that you try to fix them yourself. If you mess it up, I will correct you.
- About defining computable functions in the introduction, I moved that stuff out of the introduction specifically to make the introduction easier to read. If you use the Turing machine definition, it is completely different from the definition of primitive recursive functions and would only confuse beginners. If you use the definition with mu-recursion, then it is even more complicated than primitive recursion. So it would also confuse people. And I wanted to get the characterization of primitive recursive functions in terms of Turing machines and the Ackermann function out of the introduction because it would look like the definition which it is not.
- Use of the projections cannot be avoided without making the other stuff even worse.
- Any function which can be calculated by an actual physical computer is primitive recursive on its ___domain, but there are many primitive recursive functions which cannot be calculated by any physical computer. JRSpriggs 07:04, 19 September 2006 (UTC)
Nonsense?
I dont know how I landed up here but this doesnt makes sense !
- "The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the recursive functions (recursive functions are also known as the computable functions)."
What is primitive recursion? the article becomes denser by each word :( 122.169.148.119 (talk) 20:32, 25 November 2007 (UTC)
- Sorry, but this is a difficult concept. The definition is in the first section after the lead. However, I could over-simplify it by saying that primitive recursive functions are those which can be calculated within a predetermined number of steps (which depends on inputs). JRSpriggs (talk) 03:35, 26 November 2007 (UTC)
Critique/Suggestions To Improve the Article
This article lacks concise and comprehensive definitions of what it is trying to describe. Declaring relationships or information that may be relevant to a topic without precisely defining that topic leads to the obfuscation of and abandonment of concise definition. If you feel that the material is a difficult concept, then please abandon the approach of providing strict declarative knowledge, which really says nothing precisely about a topic at all, only relationships relevant to that topic. Since this particular topic is of interest to computer scientists, a strictly mathematical approach is of good use but not sufficient. I look forward to seeing an updated page. 14:39, 9 May 2008 —Preceding unsigned comment added by Org322001 (talk • contribs)
---
The simple one-accumulator register machine might offer a (non-strict) example of the five axioms. In this example the axioms boil down into a few primitive machine operations:
- 1 Constant function: 0 is primitive recursive: CLEAR r, (abbreviated CLR r) where "r" is any register that the machine has access to, symbolized as 0 --> r.
- Suppose we have four registers A, P, Q, R. Then CLR P will cause the contents of register P to be 0 (in other words, P will be empty of counts): 0 --> P. Registers A, Q and R will be unaffected.
- 2 Successor function: INCREMENT r (abbreviated: INC r)
- Example: INC P will add one count to register P, the contents symbolized with brackets around the register (cf. Boolos-Burgess-Jeffrey symbolism): [P]+1 --> P
- 3 Projection function: i.e. we have access to any register in the machine. We need to distinguish the two types: COPY and MOVE. COPY r1,r2 i.e. copy the contents of r2 into r1. This is easier to see if we restrict our model to a machine with a special "accumulator" register that we call "A", and the instruction "LOAD r" ( LDA r) that does the following: [r] --> A.
- Example: LDA P, symbolized [P] --> A
- Example: LOAD A,P symbolized [P] --> A
- 4 Composition: STOREA r (abbreviated: STA r). COPY the contents of A -- the contents may be the result of many operations -- into any register (including itself); the contents of A is left untouched.
- 5 Primitive recursion: The IF ... EQUALS ... THEN GOTO ... operation. We need any two of the following 3 versions:
- 5.1: IF the contents of register A EQUALS the contents of register r, then JUMP_TO instruction 7 (abbreviated: JE A,r or perhaps, JEA r)
- 5.2: IF the contents of register A is not equal to the contents of register r then GOTO instruction x (abbreviated: JNE A,r,x or perhaps JNEA r,x. 7: Jump if A is Zero to instruction 7)
- 5.3: "Unconditional jump" (JUMP_TO instruction x, appreviated J x ).
Primitive recursion actually involves incrementing too, so really, primitive recursion is an IF-THEN LOOP that counts up until the IF THEN is satisfied, at which point the function either terminates (HALT) or leaps to another instruction.
- Example: ADD the contents of register P to Q and deposit the result in R
- 1 CLEAR A ;register A is a counter to be used in the two recursions
- 2 CLEAR R :register R is where the result will appear
- ;First primitive recursive loop -- copies the count in register P into result-register R:
- ;1st primitive-recursive loop:
- 3 JEA P,7 ;Is (contents of) A equal to (contents of) P? If so then go to instruction 7 else continue to next instruction.
- 4 INC R
- 5 INC A
- 6 JUMP_TO 3
- ;1st primitive-recursive loop:
- 7 CLEAR A ;A will again be used as a counter to add the counts in Q to the counts in R
- ;2nd primitive-recursive loop:
- 8 JEA Q,12 ;Is A equal to Q? If so then go to instruction 12 else continue to next instruction.
- 9 INC R
- 10 INC A
- 11 JUMP_TO 8
- ;2nd primitive-recursive loop:
- 12 HALT ; [R]=[P]+[Q]
The above is only one version of ADD -- maybe the reader can suggest a better one -- but it illustrates the point. I don't know whether something like this would help a reader or not. One thing that comes out of it is that we know from Turing equivalence that other "instruction sets" are sufficient. Indeed, there are other sufficient axiom sets besides the "Peano set" given in this article. Who is it ... Laszlo Kalmar (1943) it was ... who originated another set similar to the counter machine (i.e. his set starts with constant 1, has INCREMENT, a subtraction (DECREMENT) and the finite sum and finite product -- these are where recursion appears (cf Kleene 1952/1971:285 and p. 526 citing Kalmar 1943). Bill Wvbailey (talk) 16:56, 9 May 2008 (UTC), slight emendation Wvbailey (talk) 18:31, 31 May 2008 (UTC)
importance
I noticed the new text on importance in the lede. While being r.e. is a nice property of the primitive recursive functions, I am not sure it is the key reason for their importance. Things that seem more important to me include:
- Most of the effective procedures that arise in elementary proof theory are primitive recursive. For example, the functions in Goedel's incompleteness theorem are all primitive recursive
- Primitive recursive arithmetic (PRA) is widely regarded as an embodiment Hilbert's finitism
- The primitive recursive functions are essy to prove total, unlike computable functions in general. In particular, they are exactly the provably total functions of RCA0.
These things ought to be in the article, actually. Unfortunately, I don't have in mind any sources that explicitly try to explain why the primitive recursive functions are important. — Carl (CBM · talk) 01:33, 23 August 2009 (UTC)
- Carl, you list three reasons. I think your first reason is certainly a nice property of PR functions, but does not distinguish them from general recursive functions. I would be interested in seeing references on your second point; perhaps the reason for this regard might be valid as a reason why the primitive recursive functions are notable. Your last point ought to be added to the reasons for notability (and I intend to do so). AshtonBenson (talk) 00:57, 28 August 2009 (UTC)
- Hrm, on second thought, I have concerns about your third point. The reason why it's easy to prove that they are total is that they are inductively generated (the totality proof proceeds by induction on the enumeration of all PR functions). So the fact that they can be proven total is important, but the reason why this is the case is because they -- as a class -- are RE. That's the "easy" you mention. AshtonBenson (talk) 00:59, 28 August 2009 (UTC)
- The class of all partial recursive functions is also r.e., as is the class of elementary functions, so it is not clear to me that this is really a unique property that makes the primitive recursive functions interesting. Can you say who makes this claim in print? — Carl (CBM · talk) 01:23, 28 August 2009 (UTC)
- The article says "subset of the set of all total recursive functions" -- the class of partial recursive functions does not meet this criteria. What makes PR notable is that it it is the strongest "common" system with all the properties mentioned (and this is what distinguishes it from the elementary functions). Now what I'm really curious to know is why, say, the primitive recursive functions plus a symbol for the Ackermann function, and closed under composition, wasn't chosen instead. I have no answer to that question. AshtonBenson (talk) 03:57, 28 August 2009 (UTC)
- P.S. The reason that the primitive recursive functions are easy to prove total is that all the induction needed to do so in arithmetic is included in the scheme , which consists of the first-order induction scheme limited to formulas. The collection of all functions primitive recursive in the Ackermann function is also r.e. and contains only total functions, but the Ackermann function itself is not provably total in RCA0. So the mere fact that the primitive recursive functions are r.e. is not the key point. — Carl (CBM · talk) 01:36, 28 August 2009 (UTC)
- If there were a name for that class of functions, and if that class had been discovered at the same time as the PR functions (or very shortly thereafter), I bet that class would be notable instead. AshtonBenson (talk) 04:01, 28 August 2009 (UTC)
- The class of all partial recursive functions is also r.e., as is the class of elementary functions, so it is not clear to me that this is really a unique property that makes the primitive recursive functions interesting. Can you say who makes this claim in print? — Carl (CBM · talk) 01:23, 28 August 2009 (UTC)
- Boolos Burgess Jeffrey 2002 say that "Another process, called (primitive) recursion, is what is involved in defining multiplication as repeated addition, exponentiation as repeated multiplication, as so on." (p. 58); we can't get what we need to do arithmetic as we know it with just "zero", "successor", "identity" and "composition". Kleene 1952:217 introduces his Chapter IX "Primitive Recursive Functions" with "To establish the lemma for Goedel's theorm, we shall develop an intuitive theory about a certain class of number-theoretic functions and predicate [etc]...". Minsky implies the machines associated with PR are "not quite so complicated" [as a Turing machine] so explorations of undecidability might be easier (p. 116). That's about all I've got. Bill Wvbailey (talk) 02:02, 23 August 2009 (UTC)
- Bill, thanks for the nice citations in which people mention PR functions, but I don't really think any of those speak to their notability (while they certainly do describe the PR functions!) AshtonBenson (talk) 00:59, 28 August 2009 (UTC)
Re Ashton, PRA: the identification of PRA with finitism is a long-running discussion in the philosophy of mathematics. Everyone I have read agrees that PRA is included in "finitism"; the point of contention is whether finitism goes beyond PRA or not, with some on each side. It is trivial to find papers where this is discussed using google. One influential paper is:
- "Remarks on finitism", Wiliam Tait, [1].
Some other works that discuss the issue are:
- "Partial realizations of Hilbert's program", Stephen Simpson, [2]
- Er, you know that this paper merely cites the one above and then moves on, right? It doesn't really add anything on this topic. AshtonBenson (talk) 04:23, 28 August 2009 (UTC)
- "Finitistic Properties of High Complexity", Dmytro Taranovsky, [3]
- "Finitism and intuitive knowledge", Charles Parsons [4]
Here is a quote from Simpson on the FOM email list in 1999 [5]:
- "Tait in his 1981 paper argued that Hilbert's finitism is formalized by PRA. This conclusion is widely accepted in the f.o.m. literature. I certainly accept it..."
There are many more references than this; the relationship between PRA and finitism has been thoroughly explored in the literature. — Carl (CBM · talk) 01:13, 28 August 2009 (UTC)
- This merely cites the same paper you cite above by Tait. There's really no additional content there. And, as a side note, I don't know if I'd count the FOMlist as a reliable source ;) AshtonBenson (talk) 04:09, 28 August 2009 (UTC)
- I guess I don't understand Astonbenson's notion of "notable", or "important". The following is certainly historically important. So I'll offer it up:
- Hilbert viewed "recursion" ("primitive", the only kind known at the time he gave his 1928) as the keystone of his formal, axiomatic theory of arithmetic. Hilbert (1926) had conjectured that there might be functions that could not be generated by [primitive] recursion, but Ackermann had not yet presented his (1928) novel "double-recursion", nor had Péter (1935) [reference: Kleene 1952:271]. So, Hilbert, in his 1927 The foundations of mathematics (van Heijenoort pp. 464ff) had only primitive recursion (based on Peano's successor and induction) at his disposal. He says "Finally, we also need explicit definitions, . . . as well as certain recursion axioms, which result from a general recursion schema. . . . For in my theory contentual inference is replaced by manipulation of signs according to rules; in this way the axiomatic method attains that reliability and perfection that it can and must reach if it is to become the basic instrument of all theoretical research."(boldface added, p. 467) He goes on about a page later to define what he means by "recursion" (nothing surprising -- the previous calculation is employed in generating the next calculation see p. 468), and after that, he states "In a corresponding way, the recursion axioms are formula systems that are modeled upon the recursive procedure. ¶ These are the general foundations of my theory. To familiarize you with the way in which it is applied I would like to adduce some examples of particular functions as they are defined by recursion." (p. 469) Here he offers examples of simple recursions starting with ι(0)=0; ι(a')=1, [etc].
- I think this strongly supports my point. Had Ackermann's function been known at the time, we probably would have wound up with some class of functions which includes it (and is closed under composition) as our most-notable class of "obviously" terminating functions (termination being obvious because the termination proof can proceed by induction on the recursive procedure for enumerating all the functions in the class). And in fact I bet we'd call them "the primitive recursive functions." Point being, that name and the notability that goes with it was given to the first-to-be-discovered "large" subset of the total recursive functions which was itself RE. AshtonBenson (talk) 04:09, 28 August 2009 (UTC)
- To sum up, "primitive" recursion provided "the general foundations" of Hilbert's theory that was to be used, in essence, by Goedel a few years later. "Full" recursion was not the driver, "primitive" recursion was. Kleene notes that the formal system he (Kleene) presents (essentially that used by Goedel 1931) "has function symbols only for the three functions ', +, *. ... This proof [Goedel's "Theorem VII: Every [primitive] recursive relation is arithmetic[al]"] is not essential to our program of formalizing number theory. If it did not succeed, we could have arranged instead that recursion equations for other functions besides + and * should be axioms of the system. ... However, it is of some interest that a finite system suffices, the more so that we can get along with the two chief functions + and * of traditional arithmetic, when taken with the logical constants and the predicate =." (boldface added, Kleene 1952:239). Bill Wvbailey (talk) 02:53, 28 August 2009 (UTC)