Talk:Primitive recursive function: Difference between revisions

Revision as of 03:57, 28 August 2009

Revision as of 03:59, 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)

:::Carl,The Iarticle guess I assumed thatsays "andsubset isof total"the wasset assumed.of all But[[total thanksrecursive for pointing this out; I've added itfunction]]s" to-- the articleclass toof distinguishpartial the PRrecursive functions fromdoes thenot partialmeet recursivethis functionscriteria. What makes PR notable is that it it is the strongest "common" system with theseall the properties mentioned (whichand this is what distinguishes it from the elementary functions). Now what I'm ''really'' curious to know is why, say, the primitive recursive functions plus a symbol for the Ackermann function, and closed under composition, wasn't chosen instead. I have no answer to that question. [[User:AshtonBenson|AshtonBenson]] ([[User talk:AshtonBenson|talk]]) 03:57, 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)