Accessible recursive functions

Bulletin of Symbolic Logic 5 (3):367-388 (1999)
  Copy   BIBTEX

Abstract

The class of all recursive functions fails to possess a natural hierarchical structure, generated predicatively from "within". On the other hand, many (proof-theoretically significant) sub-recursive classes do. This paper attempts to measure the limit of predicative generation in this context, by classifying and characterizing those (predictably terminating) recursive functions which can be successively defined according to an autonomy condition of the form: allow recursions only over well-orderings which have already been "coded" at previous levels. The question is: how can a recursion code a well-ordering? The answer lies in Girard's theory of dilators, but is reworked here in a quite different and simplified framework specific to our purpose. The "accessible" recursive functions thus generated turn out to be those provably recursive in $(\prod_{1}^{1}-CA)_{0}$

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,098

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Elementary descent recursion and proof theory.Harvey Friedman & Michael Sheard - 1995 - Annals of Pure and Applied Logic 71 (1):1-45.
Provably total functions of Basic Arithemtic.Saeed Salehi - 2003 - Mathematical Logic Quarterly 49 (3):316.
A foundation for real recursive function theory.José Félix Costa, Bruno Loff & Jerzy Mycka - 2009 - Annals of Pure and Applied Logic 160 (3):255-288.
Some restrictions on simple fixed points of the integers.G. L. McColm - 1989 - Journal of Symbolic Logic 54 (4):1324-1345.
A theory of rules for enumerated classes of functions.Andreas Schlüter - 1995 - Archive for Mathematical Logic 34 (1):47-63.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Degrees of Relative Provability.Mingzhong Cai - 2012 - Notre Dame Journal of Formal Logic 53 (4):479-489.

Analytics

Added to PP
2009-01-28

Downloads
215 (#97,448)

6 months
20 (#139,007)

Historical graph of downloads
How can I increase my downloads?

References found in this work

[product]¹2-logic, Part 1: Dilators.Jean-Yves Girard - 1981 - Annals of Mathematical Logic 21 (2):75.
Π12-logic, Part 1: Dilators.Jean-Yves Girard - 1981 - Annals of Mathematical Logic 21 (2-3):75-219.
A slow growing analogue to buchholz' proof.Toshiyasu Arai - 1991 - Annals of Pure and Applied Logic 54 (2):101-120.
An independence result for (II11-CA)+BI.Wilfried Buchholz - 1987 - Annals of Pure and Applied Logic 33 (C):131-155.

View all 9 references / Add more references