Expressing and capturing the primitive recursive functions
| Abstract | The last Episode wasn’t about logic or formal theories at all: it was about common-or-garden arithmetic and the informal notion of computability. We noted that addition can be defined in terms of repeated applications of the successor function. Multiplication can be defined in terms of repeated applications of addition. The exponential and factorial functions can be defined, in different ways, in terms of repeated applications of multiplication. There’s already a pattern emerging here! The main task in the last Episode was to get clear about this pattern. So first we said more about the idea of defining one function in terms of repeated applications of another function. Tidied up, that becomes the idea of defining a function by primitive recursion (Defn. 27). | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,653 |
| External links | This entry has no external links. Add one. |
| Through your library | Only published papers are available at libraries |
Similar books and articlesStanley S. Wainer (1999). Accessible Recursive Functions. Bulletin of Symbolic Logic 5 (3):367-388.
Joachim Lambek & Philip Scott (2005). An Exactification of the Monoid of Primitive Recursive Functions. Studia Logica 81 (1):1 - 18.
Toshiyasu Arai (1998). Variations on a Theme by Weiermann. Journal of Symbolic Logic 63 (3):897-925.
Arnold Beckmann (2002). Proving Consistency of Equational Theories in Bounded Arithmetic. Journal of Symbolic Logic 67 (1):279-296.
Michael Rathjen (1992). A Proof-Theoretic Characterization of the Primitive Recursive Set Functions. Journal of Symbolic Logic 57 (3):954-969.
Andreas Weiermann (1998). How is It That Infinitary Methods Can Be Applied to Finitary Mathematics? Gödel's T: A Case Study. Journal of Symbolic Logic 63 (4):1348-1370.
Charles Sayward (2000). Remarks on Peano Arithmetic. Russell 20:27-32.
Zlatan Damnjanovic (1994). Strictly Primitive Recursive Realizability, I. Journal of Symbolic Logic 59 (4):1210-1227.
G. L. McColm (1989). Some Restrictions on Simple Fixed Points of the Integers. Journal of Symbolic Logic 54 (4):1324-1345.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-11-28Total downloads5 ( #160,204 of 548,984 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
