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: 90,616

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

Some restrictions on simple fixed points of the integers.G. L. McColm - 1989 - Journal of Symbolic Logic 54 (4):1324-1345.
Variations on a theme by Weiermann.Toshiyasu Arai - 1998 - Journal of Symbolic Logic 63 (3):897-925.
Formal systems and recursive functions.John N. Crossley & Michael Dummett (eds.) - 1965 - Amsterdam,: North-Holland Pub. Co..
Hyper-Torre isols.Erik Ellentuck - 1981 - Journal of Symbolic Logic 46 (1):1-5.
Recursive analysis.R. L. Goodstein - 1961 - Mineola, N.Y.: Dover Publications.
Generalized weak presentations.Alexandra Shlapentokh - 2002 - Journal of Symbolic Logic 67 (2):787-819.

Analytics

Added to PP
2009-01-28

Downloads
195 (#94,125)

6 months
1 (#1,040,386)

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.

View all 9 references / Add more references