- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Computational Randomness and Lowness
Journal of Symbolic Logic 66 (3):1199-1205 (2001)
Abstract
We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0'. This contrasts with a result of Kucera and Terwijn [5] on sets that are low for the class of Martin-Lof random reals.My notes
Similar books and articles
Computational randomness and lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
Randomness, relativization and Turing degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515-535.
Schnorr randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533-554.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Lowness for the class of random sets.Antonín Kučera & Sebastiaan A. Terwijn - 1999 - Journal of Symbolic Logic 64 (4):1396-1402.
Lowness for the Class of Random Sets.Antonin Kucera & Sebastiaan Terwijn - 1999 - Journal of Symbolic Logic 64 (4):1396-1402.
Schnorr trivial reals: a construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.
Lowness for Kurtz randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Arithmetical Measure.Sebastiaan A. Terwijn & Leen Torenvliet - 1998 - Mathematical Logic Quarterly 44 (2):277-286.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
On partial randomness.Cristian S. Calude, Ludwig Staiger & Sebastiaan A. Terwijn - 2006 - Annals of Pure and Applied Logic 138 (1):20-30.
Reviewed Work(s): Lowness properties and randomness. Advances in Mathematics, vol. 197 by André Nies; Lowness for the class of Schnorr random reals. SIAM Journal on Computing, vol. 35 by Bjørn Kjos-Hanssen; André Nies; Frank Stephan; Lowness for Kurtz randomness. The Journal of Symbolic Logic, vol. 74 by Noam Greenberg; Joseph S. Miller; Randomness and lowness notions via open covers. Annals of Pure and Applied Logic, vol. 163 by Laurent Bienvenu; Joseph S. Miller; Relativizations of randomness and genericity notions. The Bulletin of the London Mathematical Society, vol. 43 by Johanna N. Y. Franklin; Frank Stephan; Liang Yu; Randomness notions and partial relativization. Israel Journal of Mathematics, vol. 191 by George Barmpalias; Joseph S. Miller; André Nies. [REVIEW]Johanna N. Y. Franklin - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
Analytics
Added to PP
2017-02-21
Downloads
0
6 months
0
2017-02-21
Downloads
0
6 months
0
Historical graph of downloads
Sorry, there are not enough data points to plot this chart.
Citations of this work
Benign cost functions and lowness properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
On Schnorr and computable randomness, martingales, and machines.Rod Downey, Evan Griffiths & Geoffrey Laforte - 2004 - Mathematical Logic Quarterly 50 (6):613-627.
Randomness and lowness notions via open covers.Laurent Bienvenu & Joseph S. Miller - 2012 - Annals of Pure and Applied Logic 163 (5):506-518.
Relativized Schnorr tests with universal behavior.Nicholas Rupprecht - 2010 - Archive for Mathematical Logic 49 (5):555-570.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-7c76586df8-5tf24 uwo