Safe recursive set functions

DOI10.1017/JSL.2015.26MaRDI QIDQ3450802zbMATH OpenOpenAlexFDO

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

Publication date 9 November 2015

Published in 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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Higher-type and set recursion theory (03D65) Turing machines and related notions (03D10)

Recommendations

• Cobham recursive set functions
• Safe Weak Minimization Revisited
• A new function algebra of EXPTIME functions by safe nested recursion
• SAFE TURING MACHINES, GRZEGORCZYK CLASSES AND POLYTIME
• scientific article; zbMATH DE number 1114331

Cites work

• scientific article; zbMATH DE number 3861143 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• Alternation
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On time-space classes and their relation to the theory of real addition
• Predicatively computable functions on sets
• The complexity of logical theories
• The fine structure of the constructible hierarchy
• \(P\neq NP\) for infinite time Turing machines

Cited in

(10)

• Cobham recursive set functions and weak set theories
• On efficiency of notations for natural numbers
• Applicable mathematics in a minimal computational theory of sets
• Cobham recursive set functions
• Predicatively computable functions on sets
• Safe recursion over an arbitrary structure: PAR, PH and DPH
• A new function algebra of EXPTIME functions by safe nested recursion
• Feasible set functions have small circuits
• Simulation of simultaneous safe recursion over an arbitrary structure
• Characterisations of variant transfinite computational models: Infinite time Turing, ordinal time Turing, and Blum–Shub–Smale machines

This page was built for publication: Safe recursive set functions

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