Preprint:
Arnold Beckmann, Samuel R. Buss, and Sy David Friedman
"Sage Recursive Set Functions"
Submitted for publication, May 2012.
Download manuscript: PDF.
Abstract:
We introduce the safe recursive set functions based on a
Bellantoni-Cook style subclass of the primitive recursive set functions.
We show 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.
We also show 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.
We characterize the safe recursive set functions on arbitrary sets
in definability-theoretic terms.
In its strongest form, we show 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, relativized to the transitive closure of the function's
arguments.
We observe that safe recursive set functions on infinite binary strings are
equivalent to functions computed by infinite-time Turing machines in
time less than ωω.
We also give a machine model for safe recursive set functions
which is based on set-indexed
parallel processors and the natural bound on running times.