Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-31T23:38:31.210Z Has data issue: false hasContentIssue false
  • English
  • Français

SAFE RECURSIVE SET FUNCTIONS

Published online by Cambridge University Press:  22 July 2015

ARNOLD BECKMANN ,
SAMUEL R. BUSS  and
SY-DAVID FRIEDMAN
ARNOLD BECKMANN
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE COLLEGE OF SCIENCE SWANSEA UNIVERSITYSWANSEA SA2 8PP, UKE-mail:[email protected]
SAMUEL R. BUSS
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA SAN DIEGO, LA JOLLA CA 92093-0112, USAE-mail:[email protected]
SY-DAVID FRIEDMAN
Affiliation:
KURT GÖDEL RESEARCH CENTER FOR MATHEMATICAL LOGIC UNIVERSITY OF VIENNA A-1090 VIENNA, AUSTRIAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Safe recursiveset functionsalternating Turing machinesinfinite time Turing machinespolynomial timerudimentary functionsJensen hierarchy
Type
Articles
Information
The Journal of Symbolic Logic , Volume 80 , Issue 3 , September 2015 , pp. 730 - 762
Copyright
Copyright © The Association for Symbolic Logic 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Arai, Toshiyasu, Predicatively computable functions on sets. Archive for Mathematical Logic, vol. 54 (2015), pp. 471–485.CrossRefGoogle Scholar
Bellantoni, Stephen and Cook, Stephen, A new recursion-theoretic characterization of the polytime functions. Computational Complexity, vol. 2 (1992), no. 2, pp. 97–110.CrossRefGoogle Scholar
Berman, Leonard, The complexity of logical theories, Theoretical Computer Science, vol. 11 (1980), pp. 71–77.CrossRefGoogle Scholar
Blum, Lenore, Shub, Mike, and Smale, Steve, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society (N.S.), vol. 21 (1989), no. 1, pp. 1–46.CrossRefGoogle Scholar
Bruss, Anna R. and Meyer, Albert R., On the time-space classes and their relation to the theory of real addition. Theoretical Computer Science, vol. 11 (1980), pp. 59–69.CrossRefGoogle Scholar
Chandra, Ashok K., Kozen, Dexter C., and Stockmeyer, Larry J., Alternation, Journal of the Association for Computing Machinery, vol. 28 (1981), pp. 114–133.CrossRefGoogle Scholar
Devlin, Keith J., Constructibility, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1984.CrossRefGoogle Scholar
Ferrante, Jeanne and Rackoff, Charles W., A decision procedure for the first order theory of real addition with order. SIAM Journal on Computing, vol. 4 (1975), no. 1, pp. 69–76.CrossRefGoogle Scholar
Friedman, Sy-David and Welch, Philip D., Two observations concerning infinite time Turing machines, BIWOC 2007 Report (Dimitriou, I., editor), Hausdorff Centre for Mathematics, Bonn, January 2007, pp. 44–47.Google Scholar
David Hamkins, Joel and Lewis, Andy, Infinite time Turing machines, this Journal, vol. 65 (2000), no. 2, pp. 567–604.Google Scholar
Jech, Thomas, Set Theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003.Google Scholar
Björn Jensen, Ronald, The fine structure of the constructible hierarchy. Annals of Mathematical Logic, vol. 4 (1972), pp. 229–308.CrossRefGoogle Scholar
Björn Jensen, Ronald and Karp, Carol, Primitive recursive set functions, Axiomatic Set Thoory (Proceedings of Symposia in Pure Mathematics, vol. XIII, Part 1, University of California, Los Angeles, California, 1967), American Mathematical Society, Providence, R.I., 1971, pp. 143–176.Google Scholar
Leivant, Daniel, Subrecursion and lambda representation over free algebras (preliminary summary), Feasible mathematics (Buss, S. and Scott, P., editors), Birkhäuser, 1990, pp. 281–292.CrossRefGoogle Scholar
Leivant, Daniel, A foundational delineation of computational feasibility, Proceedings of 6th Annual Symposium on Logic in Computer Science (LICS'91), IEEE Computer Society, 1991, pp. 2–11.Google Scholar
Sazonov, Vladimir Yu., On bounded set theory, Logic and Scientific Methods (Florence, 1995), Synthese Library, vol. 259, Kluwer Academic Publishers, Dordrecht, 1997, pp. 85–103.CrossRefGoogle Scholar
Schindler, Ralf, P ≠ NP for infinite time Turing machines. Monatshefte für Mathematik, vol. 139 (2003), no. 4, pp. 335–340.CrossRefGoogle Scholar