Streamlined subrecursive degree theory

DOI10.1016/J.APAL.2011.11.004MaRDI QIDQ408165zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1507242
• Degrees of relative provability
• Subrecursive degrees and fragments of Peano arithmetic
• A jump operator on honest subrecursive degrees
• Degrees of total algorithms versus degrees of honest functions

Cites work

• scientific article; zbMATH DE number 3125697 (Why is no real title available?)
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 1062120 (Why is no real title available?)
• scientific article; zbMATH DE number 1507242 (Why is no real title available?)
• scientific article; zbMATH DE number 922625 (Why is no real title available?)
• scientific article; zbMATH DE number 922628 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Classification of the Recursive Functions
• A Uniform Approach to Fundamental Sequences and Hierarchies
• A jump operator on honest subrecursive degrees
• Augmented loop languages and classes of computable functions
• Classical recursion theory. Vol. II
• On the density of honest subrecursive classes
• Subrecursive degrees and fragments of Peano arithmetic
• The honest subrecursive classes are a lattice

Cited in

(10)

• Semi-honest subrecursive degrees and the collection rule in arithmetic
• Dedekind cuts and long strings of zeros in base expansions
• Computable irrational numbers with representations of surprising complexity
• Degrees of total algorithms versus degrees of honest functions
• Subrecursive degrees and fragments of Peano arithmetic
• Sub-computabilities
• Interplay between insertion of zeros and the complexity of Dedekind cuts
• On the structure of the degrees of relative provability
• Honest elementary degrees and degrees of relative provability without the cupping property
• Proof lengths for instances of the Paris-Harrington principle

This page was built for publication: Streamlined subrecursive degree theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q408165)