Content deleted Content added
→importance: new section |
|||
Line 127:
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 [[User:Wvbailey|Wvbailey]] ([[User talk:Wvbailey|talk]]) 16:56, 9 May 2008 (UTC), slight emendation [[User:Wvbailey|Wvbailey]] ([[User talk: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 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)
| |||