Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-18T19:54:22.106Z Has data issue: false hasContentIssue false

A new “feasible” arithmetic

Published online by Cambridge University Press:  12 March 2014

Stephen Bellantoni
Affiliation:
Department of Computer Science, University of Toronto, Toronto, Canada, E-mail: sjb@cs.utoronto.ca
Martin Hofmann
Affiliation:
Laboratory for Foundations of Computer Science, University of Edinburgh, Edinburgh, Scotland, UK, E-mail: mxh@dcs.ed.ac.uk

Abstract

A classical quantified modal logic is used to define a “feasible” arithmetic whose provably total functions are exactly the polynomial-time computable functions. Informally, one understands ⃞∝ as “∝ is feasibly demonstrable”.

differs from a system that is as powerful as Peano Arithmetic only by the restriction of induction to ontic (i.e., ⃞-free) formulas. Thus, is defined without any reference to bounding terms, and admitting induction over formulas having arbitrarily many alternations of unbounded quantifiers. The system also uses only a very small set of initial functions.

To obtain the characterization, one extends the Curry-Howard isomorphism to include modal operations. This leads to a realizability translation based on recent results in higher-type ramified recursion. The fact that induction formulas are not restricted in their logical complexity, allows one to use the Friedman A translation directly.

The development also leads us to propose a new Frege rule, the “Modal Extension” rule: if ⊢ ∝ a then ⊢ A↔ ∝ for new symbol A.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable