Content deleted Content added
→importance: new section |
→importance: a quick look at a couple sources |
||
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)
: 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)
| |||