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

Categories

Add categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

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

Through your library

My notes

Similar books and articles

Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Image characterization and classification by physical complexity.Hector Zenil, Jean-Paul Delahaye & Cédric Gaucherel - 2012 - Complexity 17 (3):26-42.
Towards a stable definition of algorithmic randomness.Hector Zenil - unknown
Randomness Through Computation: Some Answers, More Questions.Hector Zenil (ed.) - 2011 - World Scientific.
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.
Quantum mechanics and algorithmic randomness.Ulvi Yurtsever - 2000 - Complexity 6 (1):27-34.
The application of algorithmic information theory to noisy patterned strings.Sean Devine - 2006 - Complexity 12 (2):52-58.
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.
An Extension of van Lambalgen's Theorem to Infinitely Many Relative 1-Random Reals.Kenshi Miyabe - 2010 - Notre Dame Journal of Formal Logic 51 (3):337-349.
Algorithmic randomness of continuous functions.George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber - 2008 - Archive for Mathematical Logic 46 (7-8):533-546.

Analytics

Added to PP
2013-11-23

Downloads
50 (#311,236)

6 months
4 (#790,687)

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