Talk:Primitive recursive function: Difference between revisions

Revision as of 01:23, 28 August 2009

Revision as of 01:36, 28 August 2009

Line 138:

: 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)

:::P.S. The reason that the primitive recursive functions are easy to prove total is that all the induction needed to do so in arithmetic is included in the scheme <math>I\Sigma^0_1</math>, which consists of the first-order induction scheme limited to <math>\Sigma^0_1</math> formulas. The collection of all functions primitive recursive in the Ackermann function is also r.e. and contains only total functions, but the Ackermann function itself is not provably total in RCA₀. So the mere fact that the primitive recursive functions are r.e. is not the key point. &mdash;&nbsp;Carl <small>([[User:CBM|CBM]]&nbsp;·&nbsp;[[User talk:CBM|talk]])</small> 01:36, 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)