No Cover Image

Journal article 1286 views 197 downloads

Safe Recursive Set Functions

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

The Journal of Symbolic Logic, Volume: 80, Issue: 03, Pages: 730 - 762

Swansea University Author: Arnold Beckmann Orcid Logo

DOI (Published version): 10.1017/jsl.2015.26

Abstract

This paper introduces the safe recursive set functions based on a Bellantoni-Cook style subclass of the primitive recursive set functions. It shows that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomi...

Full description

Published in: The Journal of Symbolic Logic
Published: 2015
URI: https://cronfa.swan.ac.uk/Record/cronfa20591
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: This paper introduces the safe recursive set functions based on a Bellantoni-Cook style subclass of the primitive recursive set functions. It shows that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomial growth rate functions computed by alternating exponential time Turing machines with polynomially many alternations. It also shows that the functions computed by safe recursive set functions under a more efficient binary tree encoding of finite strings by hereditarily finite sets are exactly the quasipolynomial growth rate functions computed by alternating quasipolynomial time Turing machines with polylogarithmic many alternations. The safe recursive set functions are characterized on arbitrary sets in definability-theoretic terms. In its strongest form, it is shown that a function on arbitrary sets is safe recursive if, and only if, it is uniformly definable in some polynomial level of a refinement of Jensen's J-hierarchy, relativised to the transitive closure of the function's arguments. An observation is that safe-recursive functions on infinite binary strings are equivalent to functions computed by so-called infinite-time Turing machines in time less than ωω. Finally a machine model is given for safe recursion which is based on set-indexed parallel processors and the natural bound on running times.
Keywords: Safe recursive, set functions, alternating Turing machines, infinite time Turing machines, polynomial time, rudimentary functions, Jensen hierarchy.
College: Faculty of Science and Engineering
Issue: 03
Start Page: 730
End Page: 762

Similar Items