Talk:Primitive recursive function: Difference between revisions

Revision as of 01:23, 28 August 2009

Revision as of 01:23, 28 August 2009

Line 136:

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. &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[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)

::The class of all partial recursive functions is also r.e., as is the class of elementary functions, so it is not clear to me that this is really a unique property that makes the primitive recursive functions interesting. Can you say who makes this claim in print? &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 01:23, 28 August 2009 (UTC)

: Hrm, on second thought, I have concerns about your third point. The reason why it's easy to prove that they are total is that they are inductively generated (the totality proof proceeds by induction on the enumeration of all PR functions). So the fact that they can be proven total is important, but the reason why this is the case is because they -- as a class -- are RE. That's the "easy" you mention. [[User:AshtonBenson|AshtonBenson]] ([[User talk:AshtonBenson|talk]]) 00:59, 28 August 2009 (UTC)

::The class of all partial recursive functions is also r.e., as is the class of elementary functions, so it is not clear to me that this is really a unique property that makes the primitive recursive functions interesting. Can you say who makes this claim in print? &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 01:23, 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)