Talk:Primitive recursive function

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

Contents

[edit] Old comments

Comments on previous changes:

  1. the initial set of X: they are axioms, not functions or terms. they are statements.
  2. successor: you had better not use + in the definition. we haven't defined addition.
  3. projection: the s suffix on words makes things plural.
  4. 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

[edit] 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)

[edit] Gödel's incompleteness theorem

An essential piece of Gödel's theorem uses primitive recursive functions...should that be noted here?

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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
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
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)