Document Open Access Logo

Another Characterization of the Higher K-Trivials

Authors Paul-Elliot Anglès d'Auriac, Benoit Monin

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.34.pdf
  • Filesize: 499 kB
  • 13 pages

Document Identifiers

Author Details

Paul-Elliot Anglès d'Auriac
Benoit Monin

Cite As Get BibTex

Paul-Elliot Anglès d'Auriac and Benoit Monin. Another Characterization of the Higher K-Trivials. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.34

Abstract

In algorithmic randomness, the class of K-trivial sets has proved itself to be remarkable, due to its numerous different characterizations. We pursue in this paper some work already initiated on K-trivials in the context of higher randomness. In particular we give here another characterization of the non hyperarithmetic higher K-trivial sets.

Subject Classification

Keywords
  • Algorithmic randomness
  • higher computability
  • K-triviality
  • effective descriptive set theory
  • Kolmogorov complexity

Metrics

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

References

  1. Laurent Bienvenu, Adam R Day, Noam Greenberg, Antonín Kučera, Joseph S Miller, André Nies, and Dan Turetsky. Computing k-trivial sets by incomplete random sets. The Bulletin of Symbolic Logic, 20(01):80-90, 2014. Google Scholar
  2. Laurent Bienvenu, Noam Greenberg, and Benoit Monin. Continuous higher randomness. Google Scholar
  3. Chi Tat Chong, André Nies, and Liang Yu. Lowness of higher randomness notions. Israel J. Math., 166(1):39-60, 2008. Google Scholar
  4. Chi Tat Chong and Liang Yu. Randomness in the higher setting. Submitted. Google Scholar
  5. Chi Tat Chong and Liang Yu. Recursion Theory: Computational Aspects of Definability, volume 8. Walter de Gruyter GmbH &Co KG, 2015. Google Scholar
  6. Adam R. Day and Joseph S. Miller. Cupping with random sets. Proc. Amer. Math. Soc., 142(8):2871-2879, 2014. URL: http://dx.doi.org/10.1090/S0002-9939-2014-11997-6.
  7. Rod Downey, Andre Nies, Rebecca Weber, and Liang Yu. Lowness and Π⁰₂ nullsets. J. Symbolic Logic, 71(3):1044-1052, 09 2006. URL: http://dx.doi.org/10.2178/jsl/1154698590.
  8. Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, 2010. URL: http://dx.doi.org/10.1007/978-0-387-68441-3.
  9. N. Greenberg, J. Miller, B. Monin, and D. Turetsky. Two more characterizations of k-triviality. Notre Dame Journal of Formal Logic, To appear. Google Scholar
  10. Noam Greenberg and Benoit Monin. Higher randomness and genericity. Google Scholar
  11. Joel David Hamkins and Andy Lewis. Infinite time turing machines. The Journal of Symbolic Logic, 65(02):567-604, 2000. Google Scholar
  12. Denis Hirschfeldt, André Nies, and Frank Stephan. Using random sets as oracles. Journal of the London Mathematical Society, 75(3):610-622, 2007. Google Scholar
  13. Greg Hjorth and André Nies. Randomness via effective descriptive set theory. Journal of the London Mathematical Society, 75(2):495-508, 2007. Google Scholar
  14. Alexander S. Kechris. Classical Descriptive Set Theory. Graduate Texts in Mathematics. Springer New York, 2012. Google Scholar
  15. Bjørn Kjos-Hanssen, Joseph S Miller, and Reed Solomon. Lowness notions, measure and domination. Journal of the London Mathematical Society, page jdr072, 2012. Google Scholar
  16. Per Martin-Löf. The definition of random sequences. Information and Control, 9:602-619, 1966. Google Scholar
  17. Per Martin-Löf. On the notion of randomness. Studies in Logic and the Foundations of Mathematics, 60:73-78, 1970. URL: http://dx.doi.org/10.1016/S0049-237X(08)70741-9.
  18. Benoit Monin. Higher computability and randomness. PhD thesis, Universite Paris Diderot, 2014. Google Scholar
  19. Yiannis Moschovakis. Descriptive Set Theory. Mathematical surveys and monographs. American Mathematical Society, 2009. Google Scholar
  20. André Nies. Lowness properties and randomness. Advances in Mathematics, 197(1):274-305, 2005. Google Scholar
  21. André Nies. Computability and Randomness. Oxford Logic Guides. Oxford University Press, 2009. Google Scholar
  22. Gerald E. Sacks. Higher recursion theory. Perspectives in mathematical logic. Springer-Verlag, 1990. 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 About DROPS Imprint Privacy Contact