Streamlined subrecursive degree theory

DOI10.1016/j.apal.2011.11.004zbMath1245.03063OpenAlexW2015272527MaRDI QIDQ408165

Lars Kristiansen, Jan-Christoph Schlage-Puchta, Andreas Weiermann

Publication date: 29 March 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.11.004

zbMATH Keywords

honest functionsprovability in PAsubrecursive degrees

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Semi-honest subrecursive degrees and the collection rule in arithmetic ⋮ Computable irrational numbers with representations of surprising complexity ⋮ Honest elementary degrees and degrees of relative provability without the cupping property ⋮ Proof lengths for instances of the Paris-Harrington principle ⋮ Sub-computabilities ⋮ Dedekind cuts and long strings of zeros in base expansions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A jump operator on honest subrecursive degrees
• Augmented loop languages and classes of computable functions
• On the density of honest subrecursive classes
• Classical recursion theory. Vol. II
• The honest subrecursive classes are a lattice
• A Uniform Approach to Fundamental Sequences and Hierarchies
• A Classification of the Recursive Functions
• Subrecursive degrees and fragments of Peano arithmetic