Document Open Access Logo

Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order

Authors Nikolay Bazhenov , Dariusz Kalociński , Michał Wrocławski

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.8.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Nikolay Bazhenov
  • Sobolev Institute of Mathematics, Novosibirsk, Russia
Dariusz Kalociński
  • Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland
Michał Wrocławski
  • Faculty of Philosophy, University of Warsaw, Poland

Funding

  • Bazhenov, Nikolay: The work of Bazhenov is supported by the Mathematical Center in Akademgorodok under agreement No. 075-15-2019-1613 with the Ministry of Science and Higher Education of the Russian Federation.
  • Kalociński, Dariusz: The work of Kalociński is supported by the National Science Centre Poland, grant No. 2018/31/B/HS1/04018.

Acknowledgements

We would like to thank Matthew Harrison-Trainor, Aleksander Iwanow, Mars Yamaleev for helpful discussions and anonymous reviewers for comments.

Cite AsGet BibTex

Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski. Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.8

Abstract

The intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum - the set of Turing degrees of images of the relation in all computable isomorphic copies of that structure. We investigate the intrinsic complexity of unary total recursive functions on nonnegative integers with standard order. According to existing results, the possible spectra of such functions include three sets consisting of precisely: the computable degree, all c.e. degrees and all Δ₂ degrees. These results, however, fall far short of the full classification. In this paper, we obtain a more complete picture by giving a few criteria for a function to have intrinsic complexity equal to one of the three candidate sets of degrees. Our investigations are based on the notion of block functions and a broader class of quasi-block functions beyond which all functions of interest have intrinsic complexity equal to the c.e. degrees. We also answer the questions raised by Wright [Wright, 2018] and Harrison-Trainor [Harrison-Trainor, 2018] by showing that the division between computable, c.e. and Δ₂ degrees is insufficient in this context as there is a unary total recursive function whose spectrum contains all c.e. degrees but is strictly contained in the Δ₂ degrees.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computability
Keywords
  • Computable Structure Theory
  • Degree Spectra
  • ω-Type Order
  • c.e. Degrees
  • d.c.e. Degrees
  • Δ₂ Degrees
  • Learnability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Chris J. Ash and Julia Knight. Computable structures and the hyperarithmetical hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics. Elsevier, Amsterdam, 2000. Google Scholar
  2. Jennifer Chubb, Andrey Frolov, and Valentina Harizanov. Degree spectra of the successor relation of computable linear orderings. Archive for Mathematical Logic, 48(1):7-13, 2009. URL: https://doi.org/10.1007/s00153-008-0110-6.
  3. S. Barry Cooper. Degrees of unsolvability. PhD thesis, University of Leicester, 1971. Google Scholar
  4. S. Barry Cooper, Steffen Lempp, and Philip Watson. Weak density and cupping in the d-r.e. degrees. Israel Journal of Mathematics, 67(2):137-152, 1989. URL: https://doi.org/10.1007/BF02937291.
  5. Rod Downey, Bakhadyr Khoussainov, Joseph S. Miller, and Liang Yu. Degree spectra of unary relations on (ω, ≤). In Logic, Methodology and Philosophy of Science: Proceedings of the Thirteenth International Congress, pages 35-55. College Publications, 2009. Publisher: Citeseer. URL: http://homepages.mcs.vuw.ac.nz/~downey/publications/LOJan24.pdf.
  6. Richard L. Epstein. Degrees of Unsolvability: Structure and Theory, volume 759 of Lecture Notes in Mathematics. Springer, Berlin Heidelberg, 1979. Google Scholar
  7. Ekaterina B. Fokina, Valentina Harizanov, and Alexander Melnikov. Computable model theory. In R. Downey, editor, Turing’s legacy: Developments from Turing’s ideas in logic, volume 42 of Lecture Notes in Logic, pages 124-194. Cambridge University Press, Cambridge, 2014. URL: https://doi.org/10.1017/CBO9781107338579.006.
  8. E. Mark Gold. Limiting Recursion. Journal of Symbolic Logic, 30(1):28-48, 1965. URL: https://doi.org/10.2307/2270580.
  9. Valentina S. Harizanov. Degree spectrum of a recursive relation on a recursive structure. PhD thesis, University of Wisconsin-Madinson, 1987. Google Scholar
  10. Matthew Harrison-Trainor. Degree spectra of relations on a cone. Memoirs of the American Mathematical Society, 253(1208):1-120, 2018. URL: https://doi.org/10.1090/memo/1208.
  11. Denis R. Hirschfeldt. Degree spectra of relations on computable structures. Bulletin of Symbolic Logic, 6(2):197-212, 2000. URL: https://doi.org/10.2307/421207.
  12. Carolyn Alexis Knoll. Degree spectra of unary relations on ω and ζ. Master’s thesis, University of Waterloo, 2009. Google Scholar
  13. Dragoslav S. Mitrinović, József Sándor, and Borislav Crstici. Handbook of Number Theory, volume 351 of Mathematics and Its Applications. Kluwer, 1995. Google Scholar
  14. Antonio Montalbán. Computable structure theory: Within the arithmetic. Cambridge University Press, 2021. Google Scholar
  15. Michael Moses. Relations Intrinsically Recursive in Linear Orders. Mathematical Logic Quarterly, 32(25-30):467-472, 1986. URL: https://doi.org/10.1002/malq.19860322514.
  16. Hilary Putnam. Trial and Error Predicates and the Solution to a Problem of Mostowski. Journal of Symbolic Logic, 30(1):49-57, 1965. URL: https://doi.org/10.2307/2270581.
  17. Linda Jean Richter. Degrees of structures. Journal of Symbolic Logic, 46(4):723-731, 1981. Publisher: Cambridge University Press. URL: https://doi.org/10.2307/2273222.
  18. Stewart Shapiro. Acceptable notation. Notre Dame Journal of Formal Logic, 23(1):14-20, January 1982. URL: https://doi.org/10.1305/ndjfl/1093883561.
  19. Joseph R. Shoenfield. On degrees of unsolvability. Annals of Mathematics, 69:644-653, 1959. URL: https://doi.org/10.2307/1970028.
  20. Robert I. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag, New York, NY, USA, 1987. Google Scholar
  21. Matthew Wright. Degrees of relations on ordinals. Computability, 7(4):349-365, 2018. URL: https://doi.org/10.3233/COM-180086.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact