Polynomially Bounded Recursive Realizability

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


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



    Upload a copy of this work     Papers currently archived: 89,491

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 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.


Added to PP

21 (#622,457)

6 months
3 (#428,620)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Saeed Salehi
University of Tabriz