Content deleted Content added
→importance: a quick look at a couple sources |
AshtonBenson (talk | contribs) |
||
Line 135:
* The primitive recursive functions are essy to prove total, unlike computable functions in general. In particular, they are exactly the provably total functions of RCA<sub>0</sub>.
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 <small>([[User:CBM|CBM]] · [[User talk:CBM|talk]])</small> 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). [[User:AshtonBenson|AshtonBenson]] ([[User talk:AshtonBenson|talk]]) 00:57, 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 [[User:Wvbailey|Wvbailey]] ([[User talk: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!)
| |||