Book contents
- Frontmatter
- Preface
- Contents
- TUTORIALS
- ARTICLES
- Modified bar recursion and classical dependent choice
- Choice and uniformity in weak applicative theories
- Compactness and incompactness phenomena in set theory
- Selection for Borel relations
- Interpolation in goal-directed proof systems 1
- Sequences of degrees associated with models of arithmetic
- The limit theory of generic polynomials
- Moschovakis's notion of meaning as applied to linguistics
- Tameness in expansions of the real field
- The model theory of compact complex spaces
- “Natural” representations and extensions of Gödel's second theorem 350
- Effective Hausdorff dimension
- Mutual stationarity in the coremodel
- The pair (Nn, N0) may fail N0-compactness
- Incompleteness theoremand its frontier
- Groups in Simple Theories
- References
Provable recursiveness and complexity
from ARTICLES
Published online by Cambridge University Press: 31 March 2017
By
Book contents
- Frontmatter
- Preface
- Contents
- TUTORIALS
- ARTICLES
- Modified bar recursion and classical dependent choice
- Choice and uniformity in weak applicative theories
- Compactness and incompactness phenomena in set theory
- Selection for Borel relations
- Interpolation in goal-directed proof systems 1
- Sequences of degrees associated with models of arithmetic
- The limit theory of generic polynomials
- Moschovakis's notion of meaning as applied to linguistics
- Tameness in expansions of the real field
- The model theory of compact complex spaces
- “Natural” representations and extensions of Gödel's second theorem 350
- Effective Hausdorff dimension
- Mutual stationarity in the coremodel
- The pair (Nn, N0) may fail N0-compactness
- Incompleteness theoremand its frontier
- Groups in Simple Theories
- References
- Type
- Chapter
- Information
- Logic Colloquium '01 , pp. 468 - 486Publisher: Cambridge University PressPrint publication year: 2005
References
[1] and , A new recursion theoretic characterization of the polytime functions,Computational Complexity, vol. 2 (1992), pp. 97–110.
[2] , An independence result for Π11 - CA + BI, Annals of Pure and Applied Logic, vol. 23 (1987), pp. 131–155.Google Scholar
[3] , Fragments of Heyting arithmetic,The Journal of Symbolic Logic, vol. 65 (2000), pp. 1223–1240.
[4] , , and , Proof theoretic complexity of low subrecursive classes,Foundations of secure computation ( and , editors), IOS Press, 2000, pp. 249–285.
[5] and , Hierarchies of provably recursive functions,Handbook of proof theory (, editor), Elsevier Science BV, 1998, pp. 149–207.
[6] , On the interpretation of non-finitist proofs, parts I, II,The Journal of Symbolic Logic, vol. 16 (1951), pp. 241–267, vol. 17 (1952) pp. 43–58.
[7] , A foundational delineation of poly-time,Information and Computation, vol. 110 (1994), pp. 391–420.
[8] , Intrinsic theories and computational complexity,Logic and computational complexity (, editor), Lecture Notes in Computer Science, vol. 960, Springer-Verlag, 1995, pp. 177–194.
[9] , Actual arithmetic and feasibility,Proceedings of CSL 2001 (, editor), Lecture Notes in Computer Science, vol. 2142, Springer-Verlag, 2001, pp. 115–129.
[10] , Proof theories of low subrecursive classes,Ph.D. thesis, Leeds, 1999.
[11] and , Elementary arithmetic, Leeds, preprint, 2001, to appear in Annals of Pure and Applied Logic.
[12] , Klassen rekursiver Funktionen,Proceedings of Summer School in Logic, Leeds 1967 (, editor), Lecture Notes in Mathematics, vol. 70, Springer-Verlag, 1968, pp. 159–222.
[13] and , Basic proof theory, Cambridge Tracts in Theoretical Computer Science, vol. 43, CUP, 1996.Google Scholar
[14] , How to characterize provably total functions by local predicativity,The Journal of Symbolic Logic, vol. 61 (1996), pp. 52–69.Google Scholar