On partial randomness

Annals of Pure and Applied Logic 138 (1):20-30 (2006)
  Copy   BIBTEX

Abstract

If is a random sequence, then the sequence is clearly not random; however, seems to be “about half random”. L. Staiger [Kolmogorov complexity and Hausdorff dimension, Inform. and Comput. 103 159–194 and A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst. 31 215–229] and K. Tadaki [A generalisation of Chaitin’s halting probability Ω and halting self-similar sets, Hokkaido Math. J. 31 219–253] have studied the degree of randomness of sequences or reals by measuring their “degree of compression”. This line of study leads to various definitions of partial randomness. In this paper we explore some relations between these definitions. Among other results we obtain a characterisation of Σ1-dimension in terms of strong Martin-Löf ε-tests , and we show that ε-randomness for ε is different than the classical 1-randomness

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 98,205

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

Fixed point theorems on partial randomness.Kohtaro Tadaki - 2012 - Annals of Pure and Applied Logic 163 (7):763-774.
Shift-complex sequences.Mushfeq Khan - 2013 - Bulletin of Symbolic Logic 19 (2):199-215.
The Kolmogorov complexity of random reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.

Analytics

Added to PP
2013-12-31

Downloads
18 (#986,861)

6 months
3 (#1,431,119)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Effectively closed sets of measures and randomness.Jan Reimann - 2008 - Annals of Pure and Applied Logic 156 (1):170-182.
Cone avoidance and randomness preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
Mass problems and initial segment complexity.W. M. Phillip Hudelson - 2014 - Journal of Symbolic Logic 79 (1):20-44.

View all 7 citations / Add more citations

References found in this work

Add more references