Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-12T19:45:20.463Z Has data issue: false hasContentIssue false
  • English
  • Français

Schnorr triviality and genericity

Published online by Cambridge University Press:  12 March 2014

Johanna N.Y. Franklin
Johanna N.Y. Franklin*
Affiliation:
Department of Pure Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, Ontario N2L 3G1, Canada, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the connection between Schnorr triviality and genericity. We show that while no 2-generic is Turing equivalent to a Schnorr trivial and no 1-generic is tt-equivalent to a Schnorr trivial, there is a 1-generic that is Turing equivalent to a Schnorr trivial. However, every such 1-generic must be high. As a corollary, we prove that not all K-trivials are Schnorr trivial. We also use these techniques to extend a previous result and show that the bases of cones of Schnorr trivial Turing degrees are precisely those whose jumps are at least 0″.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 1 , March 2010 , pp. 191 - 207
Copyright
Copyright © Association for Symbolic Logic 2010

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

[1] Chaitin, Gregory J., A theory of program size formally identical to information theory, Journal of the Association for Computing Machinery, vol. 22 (1975), pp. 329–340.Google Scholar
[2] Downey, Rod, Griffiths, Evan, and Laforte, Geoffrey, On Schnorr and computable randomness, martingales, and machines, Mathematical Logic Quarterly, vol. 50 (2004), no. 6, pp. 613–627.Google Scholar
[3] Downey, Rod, Hirschfeldt, Denis R., Nies, Andre, and Terwijn, Sebastiaan A., Calibrating randomness, The Bulletin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 411–491.Google Scholar
[4] Downey, Rod G., Hirschfeldt, Denis R., Nies, Andre, and Stephan, Frank, Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore University Press, Singapore, 2003, pp. 103–131.Google Scholar
[5] Downey, Rodney G. and Griffiths, Evan J., Schnorr randomness, this Journal, vol. 69 (2004), no. 2, pp. 533–554.Google Scholar
[6] Franklin, Johanna N. Y., Schnorr trivial reals: A construction, Archive for Mathematical Logic, vol. 46 (2008), no. 7–8, pp. 665–678.Google Scholar
[7] Franklin, Johanna N. Y. and Stephan, Frank, Schnorr trivial sets and truth-table reducibility, Technical Report TRA3/08, School of Computing, National University of Singapore, 2008.Google Scholar
[8] Kummer, Martin, A proof of Beigel's cardinality conjecture, this Journal, vol. 57 (1992), no. 2, pp. 677–681.Google Scholar
[9] Martin, Donald A., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.Google Scholar
[10] Nies, André, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), no. 1, pp. 274–305.Google Scholar
[11] Odifreddi, P. G., Classical recursion theory. Volume II, Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland Publishing Co., Amsterdam, 1999.Google Scholar
[12] Schnorr, C.-P., Zufälligkeit und Wahrscheintichkeit, Lecture Notes in Mathematics, vol. 218, Springer-Verlag, Heidelberg, 1971.Google Scholar
[13] Soare, Robert I., Recursively enumerable sets and degrees. Perspectives in Mathematical Logic, Springer-Verlag, 1987.Google Scholar
[14] Zambella, Domenico, On sequences with simple initial segments, Technical Report ILLC ML-1990-05, University of Amsterdam, 1990.Google Scholar