Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-03T01:01:16.382Z Has data issue: false hasContentIssue false
  • English
  • Français

Schnorr trivial sets and truth-table reducibility

Published online by Cambridge University Press:  12 March 2014

Johanna N. Y. Franklin  and
Frank Stephan
Johanna N. Y. Franklin
Affiliation:
Department of Pure Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, CanadaN2L 3G1 E-mail: [email protected]
Frank Stephan
Affiliation:
Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543. Republic of Singapore. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey. Griffiths and LaForte.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 2 , June 2010 , pp. 501 - 521
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]Arslanov, Marat, On some generalizations of a fixed-point theorem, Soviet Mathematics, vol. 25 (1981), no. 5, pp. 9–16, English translation, Izvestiya Vysshikh Uchebnykh Zavedeniĭ. Matematika. vol. 25 (1981), no. 5, pp. 1–10, Russian.Google Scholar
[2]Calude, Cristian S. and Nies, André. Chaitin Ω numbers and strong rcducibililies, Journal of Universal Computer Science, vol. 3 (1997), pp. 1162–1166.Google Scholar
[3]Downey, Rod, Griffiths, Evan, and LaForte, Geoffrey, On Schnorr and computable randomness, martingales, andmachines, Mathematical Logic Quarterly, vol. 50 (2004). 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). pp. 411–491.CrossRefGoogle Scholar
[5]Franklin, Johanna N. Y., Aspects of Schnorr randomness, Ph.D. dissertation, University of California, Berkeley, 2007.Google Scholar
[6]Franklin, Johanna N. Y., Hyperimmune-free degrees and Schnorr triviality, this Journal, vol. 73 (2008). pp. 999–1008.Google Scholar
[7]Franklin, Johanna N. Y., Schnorr trivial reals: A construction. The Archive for Mathematical Logic, vol. 46 (2008), pp. 665–678.CrossRefGoogle Scholar
[8]Franklin, Johanna N. Y., Schnorr triviality andgenericity, this Journal, vol. 75 (2010), pp. 191–207.Google Scholar
[9]Hirschfeldt, Denis, Nies, André, and Stephan, Frank, Using random sets as oracles, Journal of the London Mathematical Society, vol. 75 (2007). pp. 610–622.CrossRefGoogle Scholar
[10]Jockusch, Carl G. and Stephan, Frank, A cohesive set which is not high, Mathematical Logic Quarterly, vol. 39 (1993), pp. 515–530. A corrective note (keeping the main results intact) appeared in the same journal, vol. 43 (1997). p. 569.CrossRefGoogle Scholar
[11]Li, Ming and Vitányi, Paul, An introduction to Kolmogorov complexity and its applications, Springer, Heidelberg, 1993.CrossRefGoogle Scholar
[12]Martin-Löf, Per, The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602–619.CrossRefGoogle Scholar
[13]Mihailović, Nenad, Algorithmic randomness, Inaugural-Dissertation, University of Heidelberg, 2007.Google Scholar
[14]Miller, Webb and Martin, Donald, The degrees of hyperimmune sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 159–166.CrossRefGoogle Scholar
[15]Nies, André, Lowness properties of reals and randomness, Advances in Mathematics, vol. 197, (2005), pp. 274–305.CrossRefGoogle Scholar
[16]Nies, André, Stephan, Frank, and Terwijn, Sebastiaan A.. Randomness, relativization and Turing degrees, this Journal, vol. 70 (2005). pp. 515–535.Google Scholar
[17]Odifreddi, Piergiorgio, Classical recursion theory, North-Holland, Amsterdam, 1989.Google Scholar
[18]Odifreddi, Piergiorgio, Classical recursion theory, Volume II, North-Holland, Amsterdam, 1999.Google Scholar
[19]Rogers, Hartley, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[20]Sacks, Gerald E., A maximal set which is not complete, Michigan Mathematical Journal, vol. 11 (1964), pp. 193–205.CrossRefGoogle Scholar
[21]Schnorr, Claus Peter, Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, vol. 218, Springer, 1971.CrossRefGoogle Scholar
[22]Schnorr, Claus Peter, Process complexity and effective random tests, Journal of Computer and System Sciences, vol. 7 (1973), pp. 376–388.CrossRefGoogle Scholar
[23]Soare, Robert, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Springer-Verlag, Heidelberg, 1987.Google Scholar
[24]Stephan, Frank, The complexity of the set of nonrandom numbers, Randomness and complexity, from Leibnitz to Chaitin (Calude, Cristian S., editor), vol. 217-230, World Scientific, 2007.Google Scholar