Strahm, Thomas (1997). Polynomial time operations in explicit mathematics. The journal of symbolic logic, 62(2), pp. 575-594. Cambridge University Press 10.2307/2275547
|
Text
S0022481200016364.pdf - Published Version Available under License Publisher holds Copyright. Download (1MB) | Preview |
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.
Item Type: |
Journal Article (Original Article) |
|---|---|
Division/Institute: |
08 Faculty of Science > Institute of Computer Science (INF) |
UniBE Contributor: |
Strahm, Thomas Adrian |
Subjects: |
000 Computer science, knowledge & systems 500 Science > 510 Mathematics |
ISSN: |
0022-4812 |
Publisher: |
Cambridge University Press |
Language: |
English |
Submitter: |
Marceline Brodmann |
Date Deposited: |
28 Jul 2020 11:03 |
Last Modified: |
06 Sep 2024 09:31 |
Publisher DOI: |
10.2307/2275547 |
BORIS DOI: |
10.7892/boris.115326 |
URI: |
https://boris.unibe.ch/id/eprint/115326 |
Actions (login required)
 |
Edit item |