Mathematical Logic Quarterly 57 (3):323-338 (2011)
| Abstract |
Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
|
| Keywords | 03D25 03D15 Schnorr randomness truth‐table reducibility MSC (2010) 68Q30 van Lambalgen's Theorem computably randomness |
| Categories | (categorize this paper) |
| DOI | 10.1002/malq.200910128 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
PhilArchive copy
Upload a copy of this paper Check publisher's policy Papers currently archived: 69,066
External links
(no proxy) 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
- Sign in / register and customize your OpenURL resolver..
- Configure custom resolver
References found in this work BETA
On Schnorr and Computable Randomness, Martingales, and Machines.Rod Downey, Evan Griffiths & Geoffrey Laforte - 2004 - Mathematical Logic Quarterly 50 (6):613-627.
Kolmogorov–Loveland Randomness and Stochasticity.Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan - 2006 - Annals of Pure and Applied Logic 138 (1):183-210.
Schnorr Trivial Sets and Truth-Table Reducibility.Johanna N. Y. Franklin & Frank Stephan - 2010 - Journal of Symbolic Logic 75 (2):501-521.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
View all 8 references / Add more references
Citations of this work BETA
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Characterizing Lowness for Demuth Randomness.Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies & Dan Turetsky - 2014 - Journal of Symbolic Logic 79 (2):526-560.
Unified Characterizations of Lowness Properties Via Kolmogorov Complexity.Takayuki Kihara & Kenshi Miyabe - 2015 - Archive for Mathematical Logic 54 (3-4):329-358.
Nullifying Randomness and Genericity Using Symmetric Difference.Rutger Kuyper & Joseph S. Miller - 2017 - Annals of Pure and Applied Logic 168 (9):1692-1699.
Computable Randomness and Betting for Computable Probability Spaces.Jason Rute - 2016 - Mathematical Logic Quarterly 62 (4-5):335-366.
Similar books and articles
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Schnorr Trivial Sets and Truth-Table Reducibility.Johanna N. Y. Franklin & Frank Stephan - 2010 - Journal of Symbolic Logic 75 (2):501-521.
Probabilistic Algorithmic Randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Hyperimmune-Free Degrees and Schnorr Triviality.Johanna N. Y. Franklin - 2008 - Journal of Symbolic Logic 73 (3):999-1008.
A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.
Schnorr Trivial Reals: A Construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Lowness and $\pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.
An Extension of van Lambalgen's Theorem to Infinitely Many Relative 1-Random Reals.Kenshi Miyabe - 2010 - Notre Dame Journal of Formal Logic 51 (3):337-349.
Independence, Randomness and the Axiom of Choice.Michiel van Lambalgen - 1992 - Journal of Symbolic Logic 57 (4):1274-1304.
Analytics
Added to PP index
2013-12-01
Total views
48 ( #233,933 of 2,498,786 )
Recent downloads (6 months)
1 ( #421,542 of 2,498,786 )
2013-12-01
Total views
48 ( #233,933 of 2,498,786 )
Recent downloads (6 months)
1 ( #421,542 of 2,498,786 )
How can I increase my downloads?
Downloads
