Safe recursive set functions

DOI10.1017/JSL.2015.26zbMATH Open1357.03075OpenAlexW1823991804MaRDI QIDQ3450802FDOQ3450802

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

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

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)

Cites Work

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

Cited In (10)

• 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
• On efficiency of notations for natural numbers
• Cobham recursive set functions
• A new function algebra of EXPTIME functions by safe nested recursion
• Cobham recursive set functions and weak set theories
• Applicable mathematics in a minimal computational theory of sets
• Safe recursion over an arbitrary structure: PAR, PH and DPH
• Predicatively computable functions on sets

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)