Algorithmic randomness and measures of complexity

Association for Symbolic Logic: The Bulletin of Symbolic Logic (forthcoming)
  Copy   BIBTEX

Abstract

We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability

Links

PhilArchive



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

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

Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Chance versus Randomness.Antony Eagle - 2010 - Stanford Encyclopedia of Philosophy.
Probabilistic algorithmic randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Relative Randomness and Cardinality.George Barmpalias - 2010 - Notre Dame Journal of Formal Logic 51 (2):195-205.
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.
Lowness and $\Pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.

Analytics

Added to PP
2013-11-23

Downloads
50 (#325,606)

6 months
2 (#1,249,707)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Kolmogorov complexity and computably enumerable sets.George Barmpalias & Angsheng Li - 2013 - Annals of Pure and Applied Logic 164 (12):1187-1200.

Add more citations

References found in this work

No references found.

Add more references