Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-25T08:16:47.765Z Has data issue: false hasContentIssue false
  • English
  • Français

Hyperimmune-free degrees and Schnorr triviality

Published online by Cambridge University Press:  12 March 2014

Johanna N. Y. Franklin
Johanna N. Y. Franklin*
Affiliation:
Department of Mathematics, National University of Singapore, 2, Science Drive 2 Singapore 117543, Singapore, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate the relationship between lowness for Schnorr randomness and Schnorr triviality. We show that a real is low for Schnorr randomness if and only if it is Schnorr trivial and hyperimmune free.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 3 , September 2008 , pp. 999 - 1008
Copyright
Copyright © Association for Symbolic Logic 2008

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.CrossRefGoogle Scholar
[2]Demuth, Osvald, Remarks on the structure of tt-degrees based on constructive measure theory, Commentationes Mathematicae Universitatis Carolinae, vol. 29 (1988), no. 2, pp. 233–247.Google Scholar
[3]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.CrossRefGoogle Scholar
[4]Downey, Rod, Hirschfeldt, Denis R., Nies, André, and Terwijn, Sebastiaan A., Calibrating randomness, The Bulletin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 411–491.CrossRefGoogle 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.CrossRefGoogle Scholar
[7]Franklin, Johanna N. Y. and Stephan, Frank, Schnorr trivial sets and truth-table reducibility, submitted.Google Scholar
[8]Jockusch, Carl G. Jr., Relationships between reducibilities, Transactions of the American Mathematical Society, vol. 142 (1969), pp. 229–237.CrossRefGoogle Scholar
[9]Kjos-Hanssen, Bjørn, Nies, André, and Stephan, Frank, Lowness for the class of Schnorr random reals, SIAM Journal on Computing, vol. 35 (2005), no. 3, pp. 647–657 (electronic).CrossRefGoogle Scholar
[10]Miller, Joseph S. and Nies, André, Randomness and computability: Open questions, The Bulletin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 390–410.CrossRefGoogle Scholar
[11]Nies, André, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), no. 1, pp. 274–305.CrossRefGoogle Scholar
[12]Nies, André, Stephan, Frank, and Terwijn, Sebastiaan A., Randomness, relativization and Turing degrees, this Journal, vol. 70 (2005), no. 2, pp. 515–535.Google Scholar
[13]Schnorr, C.-P., A unified approach to the definition of random sequences. Mathematical Systems Theory. An International Journal on Mathematical Computing Theory, vol. 5 (1971), pp. 246–258.CrossRefGoogle Scholar
[14]Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, 1987.CrossRefGoogle Scholar
[15]Terwijn, Sebastiaan A. and Zambella, Domenico, Computational randomness and lowness, this Journal, vol. 66 (2001), no. 3, pp. 1199–1205.Google Scholar