Journal of Symbolic Logic 62 (2):575-594 (1997)

Abstract
In this paper we study (self)-applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on W = {0, 1} * are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275547
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,064
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Definedness.Solomon Feferman - 1995 - Erkenntnis 43 (3):295 - 320.
Elementary Explicit Types and Polynomial Time Operations.Daria Spescha & Thomas Strahm - 2009 - Mathematical Logic Quarterly 55 (3):245-258.

View all 7 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
227 ( #40,920 of 2,427,711 )

Recent downloads (6 months)
4 ( #181,048 of 2,427,711 )

How can I increase my downloads?

Downloads

My notes