Schnorr trivial reals: a construction [Book Review]

Archive for Mathematical Logic 46 (7-8):665-678 (2008)

Abstract
A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}$ (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if ${{\bf h'} \geq_T {\bf 0''}}$ , then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees
Keywords Randomness  Triviality  Schnorr trivial
Categories No categories specified
(categorize this paper)
DOI 10.1007/s00153-007-0061-3
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,607
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Calibrating Randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Computational Randomness and Lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 14 (7-12):159-166.

View all 7 references / Add more references

Citations of this work BETA

Hyperimmune-Free Degrees and Schnorr Triviality.Johanna N. Y. Franklin - 2008 - Journal of Symbolic Logic 73 (3):999-1008.
Schnorr Triviality and Genericity.Johanna N. Y. Franklin - 2010 - Journal of Symbolic Logic 75 (1):191-207.

Add more citations

Similar books and articles

Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Schnorr Triviality and Genericity.Johanna N. Y. Franklin - 2010 - Journal of Symbolic Logic 75 (1):191-207.
Hyperimmune-Free Degrees and Schnorr Triviality.Johanna N. Y. Franklin - 2008 - Journal of Symbolic Logic 73 (3):999-1008.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Relativized Schnorr Tests with Universal Behavior.Nicholas Rupprecht - 2010 - Archive for Mathematical Logic 49 (5):555-570.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Computational Randomness and Lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Truth-Table Schnorr Randomness and Truth-Table Reducible Randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Uniform Distribution and Algorithmic Randomness.Jeremy Avigad - 2013 - Journal of Symbolic Logic 78 (1):334-344.

Analytics

Added to PP index
2013-11-23

Total views
6 ( #855,707 of 2,325,500 )

Recent downloads (6 months)
2 ( #703,994 of 2,325,500 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature