A Counterexample to Polynomially Bounded Realizability of Basic Arithmetic

, &
Notre Dame Journal of Formal Logic 60 (3):481-489 (2019)
  Copy   BIBTEX

Abstract

We give a counterexample to the claim that every provably total function of Basic Arithmetic is a polynomially bounded primitive recursive function.

Categories

Keywords

Reprint years

DOI

10.1215/00294527-2019-0013

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,337

External links

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

Through your library

My notes

Similar books and articles

Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Provably total functions of Basic Arithemtic.Saeed Salehi - 2003 - Mathematical Logic Quarterly 49 (3):316.
Strictly Primitive Recursive Realizability, II. Completeness with Respect to Iterated Reflection and a Primitive Recursive $\omega$ -Rule.Zlatan Damnjanovic - 1998 - Notre Dame Journal of Formal Logic 39 (3):363-388.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
An Independence Result on Weak Second Order Bounded Arithmetic.Satoru Kuroda - 2001 - Mathematical Logic Quarterly 47 (2):183-186.
The provably total functions of basic arithmetic and its extensions.Mohammad Ardeshir, Erfan Khaniki & Mohsen Shahriari - forthcoming - Archive for Mathematical Logic:1-53.
Extracting Algorithms from Intuitionistic Proofs.Fernando Ferreira & António Marques - 1998 - Mathematical Logic Quarterly 44 (2):143-160.
Finite reverse mathematics.Harvey Friedman - manuscript
Elementary realizability.Zlatan Damnjanovic - 1997 - Journal of Philosophical Logic 26 (3):311-339.
Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded arithmetic and the polynomial hierarchy. Ibid., vol. 52 , pp. 143–153. - Samuel R. Buss. Relating the bounded arithmetic and polynomial time hierarchies. Ibid., vol. 75 , pp. 67–77. - Domenico Zambella. Notes on polynomially bounded arithmetic. The journal of symbolic logic, vol. 61 , pp. 942–966. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.

Analytics

Added to PP
2019-07-04

Downloads
39 (#577,026)

6 months
7 (#706,906)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Basic Predicate Calculus.Wim Ruitenburg - 1998 - Notre Dame Journal of Formal Logic 39 (1):18-46.
Provably total functions of Basic Arithemtic.Saeed Salehi - 2003 - Mathematical Logic Quarterly 49 (3):316.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
An Introduction to Basic Arithmetic.Mohammad Ardeshir & Bardyaa Hesaam - 2008 - Logic Journal of the IGPL 16 (1):1-13.

Add more references