- 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
Characterizing Lowness for Demuth Randomness
Journal of Symbolic Logic 79 (2):526-560 (2014)
Abstract
We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.Other Versions
No versions found
My notes
Similar books and articles
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
Ω-change randomness and weak Demuth randomness.Johanna N. Y. Franklin & Keng Meng Ng - 2014 - Journal of Symbolic Logic 79 (3):776-791.
André Nies. Lowness properties and randomness. Advances in Mathematics, vol. 197 , no. 1, pp. 274–305. - Bjørn Kjos-Hanssen, André Nies, and Frank Stephan. Lowness for the class of Schnorr random reals. SIAM Journal on Computing, vol. 35 , no. 3, pp. 647–657. - Noam Greenberg and Joseph S. Miller. Lowness for Kurtz randomness. The Journal of Symbolic Logic, vol. 74 , no. 2, pp. 665–678. - Laurent Bienvenu and Joseph S. Miller. Randomness and lowness notions via open covers. Annals of Pure and Applied Logic, vol. 163 , no. 5, pp. 506–518. - Johanna N. Y. Franklin, Frank Stephan, and Liang. Yu Relativizations of randomness and genericity notions. The Bulletin of the London Mathematical Society, vol. 43 , no. 4, pp. 721–733. - George Barmpalias, Joseph S. Miller, and André Nies. Randomness notions and partial relativization. Israel Journal of Mathematics, vol. 191 , no. 2, pp. 791–816. [REVIEW]Johanna N. Y. Franklin - 2013 - Bulletin of Symbolic Logic 19 (1):115-118.
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.
Demuth’s path to randomness.Antonín Kučera, André Nies & Christopher P. Porter - 2015 - Bulletin of Symbolic Logic 21 (3):270-305.
Lowness and Π₂⁰ nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044-1052.
Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Continuous higher randomness.Laurent Bienvenu, Noam Greenberg & Benoit Monin - 2017 - Journal of Mathematical Logic 17 (1):1750004.
Lowness for effective Hausdorff dimension.Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Daniel D. Turetsky & Rebecca Weber - 2014 - Journal of Mathematical Logic 14 (2):1450011.
Randomness, relativization and Turing degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - Journal of Symbolic Logic 70 (2):515-535.
Analytics
Added to PP
2016-06-30
Downloads
28 (#894,100)
6 months
4 (#1,015,689)
2016-06-30
Downloads
28 (#894,100)
6 months
4 (#1,015,689)
Historical graph of downloads
Citations of this work
Demuth’s path to randomness.Antonín Kučera, André Nies & Christopher P. Porter - 2015 - Bulletin of Symbolic Logic 21 (3):270-305.
Strong Jump-Traceability.Noam Greenberg & Dan Turetsky - 2018 - Bulletin of Symbolic Logic 24 (2):147-164.
References found in this work
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7-12):159-166.
Mass problems and hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
Lowness properties and approximations of the jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - Annals of Pure and Applied Logic 152 (1):51-66.
On Schnorr and computable randomness, martingales, and machines.Rod Downey, Evan Griffiths & Geoffrey Laforte - 2004 - Mathematical Logic Quarterly 50 (6):613-627.
Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
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-54b44b69b7-k24bk uwo