Undecidable complexity statements in -arithmetic

DOI10.2307/2274857MaRDI QIDQ3480020zbMATH OpenOpenAlexFDO

Authors 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

Ackermann's functionFree variable systemshierarchiesordinal recursionprimitive recursion

Mathematics Subject Classification ID

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

Recommendations

• A Free-Variable Theory of Primitive Recursive Arithmetic
• scientific article; zbMATH DE number 1342252
• scientific article; zbMATH DE number 1531213
• On some generalizations of the primitive recursive arithmetic
• New Computational Paradigms

Cites work

• Can programming be liberated from the von Neumann style?
• Hierarchies of number-theoretic functions II
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• Nested recursion

Cited in

(3)

• A Free-Variable Theory of Primitive Recursive Arithmetic
• scientific article; zbMATH DE number 3557777 (Why is no real title available?)
• scientific article; zbMATH DE number 6302892 (Why is no real title available?)

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

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