News
Mar 19, 2011. Added citation information
Mar 7, 2011. Published online
May 18, 2010. The paper “Truth-table Schnorr randomness and truth-table reducible randomness” is accepted by Mathematical Logic Quarterly on May 18, 2010.
Title
Truth-table Schnorr randomness and truth-table reducible randomness
Type
Fullpaper
Journal
Mathematical Logic Quarterly 57(3):323-338, 2011
DOI 10.1002/malq.200910128
Journal Page
Download
preprint
Japanese summary
Abstract
Schnorr randomness and computably 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 (defined by Franklin and Stephan too only by martingales) 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.
Cited by
@article{franklin2009van,
title={{van Lambalgen’s Theorem and high degrees}},
author={Franklin, J.N.Y. and Stephan, F.},
year={2009},
publisher={Submitted}
}
@misc{bienvenucharacterizing,
title={Characterizing lowness for Demuth randomness},
author={Bienvenu, L. and Downey, R. and Greenberg, N. and Nies, A. and Turetsky, D.},
publisher={Submitted}
}