Talk:Primitive recursive function
From Wikipedia, the free encyclopedia
Contents |
[edit] 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
[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)
