Undecidable complexity statements in -arithmetic

DOI10.2307/2274857zbMath0702.03016OpenAlexW2275260250MaRDI QIDQ3480020

Ron Sigal

Publication date: 1989

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2274857

zbMATH Keywords

hierarchiesprimitive recursionAckermann's functionordinal recursionFree variable systems

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20) Hierarchies of computability and definability (03D55)

Cites Work

• Unnamed Item
• Nested recursion
• Can programming be liberated from the von Neumann style?
• Hierarchies of number-theoretic functions II

This page was built for publication: Undecidable complexity statements in -arithmetic