SAFE RECURSIVE SET FUNCTIONS

DOI10.1017/jsl.2015.26zbMath1357.03075OpenAlexW1823991804MaRDI QIDQ3450802

Arnold Beckmann, Samuel R. Buss, Sy-David Friedman

Publication date: 9 November 2015

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

Full work available at URL: https://cronfa.swan.ac.uk/Record/cronfa20591/Download/0020591-07052015214543.pdf

zbMATH Keywords

polynomial timeset functionsalternating Turing machinesinfinite-time Turing machinesrudimentary functionsJensen hierarchysafe recursive

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10) Higher-type and set recursion theory (03D65)

Related Items

On efficiency of notations for natural numbers ⋮ Cobham recursive set functions ⋮ Applicable Mathematics in a Minimal Computational Theory of Sets ⋮ Characterisations of variant transfinite computational models: Infinite time Turing, ordinal time Turing, and Blum–Shub–Smale machines ⋮ Predicatively computable functions on sets

Cites Work

• Unnamed Item
• On time-space classes and their relation to the theory of real addition
• The complexity of logical theories
• A new recursion-theoretic characterization of the polytime functions
• \(P\neq NP\) for infinite time Turing machines
• Predicatively computable functions on sets
• Alternation
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The fine structure of the constructible hierarchy

This page was built for publication: SAFE RECURSIVE SET FUNCTIONS