Expressing and capturing the primitive recursive functions
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||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Variations on a Theme by Weiermann.Toshiyasu Arai - 1998 - Journal of Symbolic Logic 63 (3):897-925.
Proving Consistency of Equational Theories in Bounded Arithmetic.Arnold Beckmann - 2002 - Journal of Symbolic Logic 67 (1):279-296.
A Proof-Theoretic Characterization of the Primitive Recursive Set Functions.Michael Rathjen - 1992 - Journal of Symbolic Logic 57 (3):954-969.
How is It That Infinitary Methods Can Be Applied to Finitary Mathematics? Gödel's T: A Case Study.Andreas Weiermann - 1998 - Journal of Symbolic Logic 63 (4):1348-1370.
Remarks on Peano Arithmetic.Charles Sayward - 2000 - Russell: The Journal of Bertrand Russell Studies 20 (1):27-32.
Strictly Primitive Recursive Realizability, I.Zlatan Damnjanovic - 1994 - Journal of Symbolic Logic 59 (4):1210-1227.
Some Restrictions on Simple Fixed Points of the Integers.G. L. McColm - 1989 - Journal of Symbolic Logic 54 (4):1324-1345.
Added to index2009-11-28
Total downloads5 ( #595,687 of 2,164,296 )
Recent downloads (6 months)0
How can I increase my downloads?