Truth-table Schnorr randomness and truth-table reducible randomness

Mathematical Logic Quarterly 57 (3):323-338 (2011)
  Copy   BIBTEX

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 89,378

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.
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.
Independence, randomness and the axiom of choice.Michiel van Lambalgen - 1992 - Journal of Symbolic Logic 57 (4):1274-1304.

Analytics

Added to PP
2013-12-01

Downloads
49 (#283,254)

6 months
1 (#1,005,371)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Computable randomness and betting for computable probability spaces.Jason Rute - 2016 - Mathematical Logic Quarterly 62 (4-5):335-366.
Nullifying randomness and genericity using symmetric difference.Rutger Kuyper & Joseph S. Miller - 2017 - Annals of Pure and Applied Logic 168 (9):1692-1699.

Add more citations

References found in this work

On relative randomness.Antonín Kučera - 1993 - Annals of Pure and Applied Logic 63 (1):61-67.
Lowness for the class of random sets.Antonín Kučera & Sebastiaan A. Terwijn - 1999 - Journal of Symbolic Logic 64 (4):1396-1402.

View all 8 references / Add more references