Polynomially Bounded Recursive Realizability

Notre Dame Journal of Formal Logic 46 (4):407-417 (2005)

Abstract

A polynomially bounded recursive realizability, in which the recursive functions used in Kleene's realizability are restricted to polynomially bounded functions, is introduced. It is used to show that provably total functions of Ruitenburg's Basic Arithmetic are polynomially bounded (primitive) recursive functions. This sharpens our earlier result where those functions were proved to be primitive recursive. Also a polynomially bounded schema of Church's Thesis is shown to be polynomially bounded realizable. So the schema is consistent with Basic Arithmetic, whereas it is inconsistent with Heyting Arithmetic

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,660

External links

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

Through your library

Analytics

Added to PP
2010-08-24

Downloads
17 (#641,793)

6 months
2 (#259,525)

Historical graph of downloads
How can I increase my downloads?

Similar books and articles

Elementary Realizability.Zlatan Damnjanovic - 1997 - Journal of Philosophical Logic 26 (3):311-339.
Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Strictly Primitive Recursive Realizability, I.Zlatan Damnjanovic - 1994 - Journal of Symbolic Logic 59 (4):1210-1227.
0-1 Laws for Recursive Structures.E. Grädel & A. Malmström - 1999 - Archive for Mathematical Logic 38 (4-5):205-215.
Bounded Modified Realizability.Fernando Ferreira & Ana Nunes - 2006 - Journal of Symbolic Logic 71 (1):329 - 346.
Multiple Realizability.Eric Funkhouser - 2007 - Philosophy Compass 2 (2):303–315.
A General Notion of Realizability.Lars Birkedal - 2002 - Bulletin of Symbolic Logic 8 (2):266-282.

Author's Profile

Saeed Salehi
University of Tabriz

References found in this work

On the Scheme of Induction for Bounded Arithmetic Formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (3):261-302.
Basic Predicate Calculus.Wim Ruitenburg - 1998 - Notre Dame Journal of Formal Logic 39 (1):18-46.
Elementary Realizability.Zlatan Damnjanovic - 1997 - Journal of Philosophical Logic 26 (3):311-339.

View all 9 references / Add more references