Calibrating randomness

Bulletin of Symbolic Logic 12 (3):411-491 (2006)
  Copy   BIBTEX


We report on some recent work centered on attempts to understand when one set is more random than another. We look at various methods of calibration by initial segment complexity, such as those introduced by Solovay [125], Downey, Hirschfeldt, and Nies [39], Downey, Hirschfeldt, and LaForte [36], and Downey [31]; as well as other methods such as lowness notions of Kučera and Terwijn [71], Terwijn and Zambella [133], Nies [101, 100], and Downey, Griffiths, and Reid [34]; higher level randomness notions going back to the work of Kurtz [73], Kautz [61], and Solovay [125]; and other calibrations of randomness based on definitions along the lines of Schnorr [117].These notions have complex interrelationships, and connections to classical notions from computability theory such as relative computability and enumerability. Computability figures in obvious ways in definitions of effective randomness, but there are also applications of notions related to randomness in computability theory. For instance, an exciting by-product of the program we describe is a more-or-less naturalrequirement-freesolution to Post's Problem, much along the lines of the Dekker deficiency set.



    Upload a copy of this work     Papers currently archived: 92,907

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

Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Lowness and $\Pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.
Chance versus Randomness.Antony Eagle - 2010 - Stanford Encyclopedia of Philosophy.
Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
Randomness Is Unpredictability.Antony Eagle - 2005 - British Journal for the Philosophy of Science 56 (4):749-790.


Added to PP

89 (#195,093)

6 months
14 (#199,983)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Probabilities over rich languages, testing and randomness.Haim Gaifman & Marc Snir - 1982 - Journal of Symbolic Logic 47 (3):495-548.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7-12):159-166.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7‐12):159-166.
Computational randomness and lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.

View all 24 references / Add more references