Document Open Access Logo

Degree Spectra, and Relative Acceptability of Notations

Authors Nikolay Bazhenov , Dariusz Kalociński

PDF
Thumbnail PDF

File

LIPIcs.CSL.2023.11.pdf
  • Filesize: 0.82 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

Funding

  • Bazhenov, Nikolay: The work of Bazhenov is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2022-281 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 under the agreement No. 2018/31/B/HS1/04018.

Acknowledgements

We would like to thank Matthew Harrison-Trainor and Michał Wrocławski for helpful discussions and anonymous reviewers for their comments.

Cite AsGet BibTex

Nikolay Bazhenov and Dariusz Kalociński. Degree Spectra, and Relative Acceptability of Notations. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.CSL.2023.11

Abstract

We investigate the interplay between the degree spectrum of a computable relation R on the computable structure (ω, <), i.e., natural numbers with the standard order, and the computability of the successor, relativized to that relation, in all computable copies of the structure - the property we dub successor’s recoverability. In computable structure theory, this property is used to show that of all possible Turing degrees that could belong to the spectrum of R (namely, of all Δ₂ degrees), in fact only the computably enumerable degrees are contained in the spectrum. Interestingly, successor’s recoverability (in the unrelativized form) appears also in philosophy of computing where it is used to distinguish between acceptable and deviant encodings (notations) of natural numbers. Since Shapiro’s notations are rarely seen through the lens of computable structure theory, we first lay the elementary conceptual groundwork to understand notations in terms of computable structures and show how results pertinent to the former can fundamentally inform our understanding of the latter. Secondly, we prove a new result which shows that for a large class of computable relations (satisfying a certain effectiveness condition), having all c.e. degrees as a spectrum implies that the successor is recoverable from the relation. The recoverability of successor may be otherwise seen as relativized acceptability of every notation for the structure. We end with remarks about connections of our result to relative computable categoricity and to a similar direction pursued by Matthew Harrison-Trainor in [Harrison-Trainor, 2018], and with an open question.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computability
Keywords
  • Computable structure theory
  • Degree spectra
  • ω-type order
  • C.e. degrees
  • Δ₂ degrees
  • Acceptable notation
  • Successor
  • 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. Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski. Intrinsic complexity of recursive functions on natural numbers with standard order. In Petra Berenbrink and Benjamin Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1-8:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2022.8.
  3. Paul Benacerraf. What numbers could not be. The Philosophical Review, 74(1):47-73, 1965. URL: https://doi.org/10.2307/2183530.
  4. Paul Benacerraf. Recantation or Any old ω-sequence would do after all. Philosophia Mathematica, 4(2):184-189, 1996. URL: https://doi.org/10.1093/philmat/4.2.184.
  5. Jennifer Chubb, Andrey Frolov, and Valentina S. 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.
  6. Alonzo Church. An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2):345-363, 1936. URL: https://doi.org/10.2307/2371045.
  7. S. Barry Cooper. Degrees of unsolvability. PhD thesis, University of Leicester, 1971. Google Scholar
  8. Brian Jack Copeland and Diane Proudfoot. Deviant encodings and Turing’s analysis of computability. Studies in History and Philosophy of Science Part A, 41(3):247-252, 2010. Google Scholar
  9. Nigel Cutland. Computability: An Introduction to Recursive Function Theory. Cambridge University Press, Cambridge, MA, 1980. Google Scholar
  10. 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. URL: http://homepages.mcs.vuw.ac.nz/~downey/publications/LOJan24.pdf.
  11. Yurii L. Ershov. A hierarchy of sets. I. Algebra and Logic, 7(1):25-43, 1968. URL: https://doi.org/10.1007/BF02218750.
  12. Yurii L. Ershov. On a hierarchy of sets, II. Algebra and Logic, 7(4):212-232, 1968. URL: https://doi.org/10.1007/BF02218664.
  13. Yurii L. Ershov. On a hierarchy of sets. III. Algebra and Logic, 9(1):20-31, 1970. URL: https://doi.org/10.1007/BF02219847.
  14. Ekaterina B. Fokina, Valentina S. 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.
  15. E. Mark Gold. Limiting Recursion. Journal of Symbolic Logic, 30(1):28-48, 1965. URL: https://doi.org/10.2307/2270580.
  16. Sergey S. Goncharov. Autostability and computable families of constructivizations. Algebra and Logic, 14(6):392-409, 1975. URL: https://doi.org/10.1007/BF01668470.
  17. Valentina S. Harizanov. Degree spectrum of a recursive relation on a recursive structure. PhD thesis, University of Wisconsin-Madinson, 1987. Google Scholar
  18. 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.
  19. 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.
  20. Dariusz Kalociński and Michał Wrocławski. Generalization of Shapiro’s theorem to higher arities and noninjective notations. Archive for Mathematical Logic, September 2022. URL: https://doi.org/10.1007/s00153-022-00836-4.
  21. Julia F. Knight. Degrees coded in jumps of orderings. Journal of Symbolic Logic, 51(4):1034-1042, 1986. URL: https://doi.org/10.2307/2273915.
  22. Steffen Lempp. Priority arguments in computability theory, model theory, and complexity theory, 2012. preprint available on the author’s webpage. URL: https://people.math.wisc.edu/~lempp/papers/prio.pdf.
  23. Anatolii I. Mal'tsev. Constructive algebras. I. Russian Mathematical Surveys, 16(3):77-129, 1961. URL: https://doi.org/10.1070/RM1961v016n03ABEH001120.
  24. Anatolii I. Mal'tsev. On recursive abelian groups. Soviet Mathematics. Doklady, 3:1431-1434, 1962. Google Scholar
  25. Andrei A. Markov. The theory of algorithms. Trudy Matematicheskogo Instituta imeni V.A. Steklova, 38:176-189, 1951. in Russian. Google Scholar
  26. Antonio Montalbán. Computable structure theory: Within the arithmetic. Cambridge University Press, 2021. Google Scholar
  27. 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.
  28. 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.
  29. Paula Quinon. A taxonomy of deviant encodings. In Florin Manea, Russell G. Miller, and Dirk Nowotka, editors, Sailing Routes in the World of Computation, volume 10936 of LNCS, pages 338-348, Cham, 2018. Springer International Publishing. Google Scholar
  30. Michael Rescorla. Church’s Thesis and the conceptual analysis of computability. Notre Dame Journal of Formal Logic, 48(2):253-280, 2007. URL: https://doi.org/10.1305/ndjfl/1179323267.
  31. Linda J. C. Richter. Degrees of Unsolvability of Models. PhD thesis, University of Illinois at Urbana-Champaign, 1977. Google Scholar
  32. Linda J. C. Richter. Degrees of structures. Journal of Symbolic Logic, 46(4):723-731, 1981. URL: https://doi.org/10.2307/2273222.
  33. Hartley Rogers. Theory of recursive functions and effective computability. MIT Press, Cambridge, MA, 1987. Google Scholar
  34. Stewart Shapiro. Acceptable notation. Notre Dame Journal of Formal Logic, 23(1):14-20, 1982. URL: https://doi.org/10.1305/ndjfl/1093883561.
  35. Stewart Shapiro, Eric Snyder, and Richard Samuels. Computability, notation, and de re knowledge of numbers. Philosophies, 7(1), 2022. URL: https://doi.org/10.3390/philosophies7010020.
  36. John C. Shepherdson and Howard E. Sturgis. Computability of recursive functions. Journal of the ACM, 10(2):217-255, 1963. URL: https://doi.org/10.1145/321160.321170.
  37. Robert I. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag, New York, 1987. Google Scholar
  38. Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Ser. 2, 42:230-265, 1936. URL: https://doi.org/10.1112/plms/s2-42.1.230.
  39. Matthew Wright. Degrees of relations on ordinals. Computability, 7(4):349-365, 2018. URL: https://doi.org/10.3233/COM-180086.
  40. Michał Wrocławski. Representations of numbers and their computational properties. PhD thesis, University of Warsaw, Warsaw, 2019. Google Scholar
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