Algorithmic Randomness and Measures of Complexity

Bulletin of Symbolic Logic 19 (3):318-350 (2013)
  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 reducibilities that measure the initial segment complexity of reals and 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

Keywords

Reprint years

DOI

10.1017/s1079898600010672

Links

PhilArchive



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

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

Algorithmic randomness and measures of complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
Algorithmic randomness and measures of complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
Constructive equivalence relations on computable probability measures.Laurent Bienvenu & Wolfgang Merkle - 2009 - Annals of Pure and Applied Logic 160 (3):238-254.
Image characterization and classification by physical complexity.Hector Zenil, Jean-Paul Delahaye & Cédric Gaucherel - 2012 - Complexity 17 (3):26-42.
Randomness Through Computation: Some Answers, More Questions.Hector Zenil (ed.) - 2011 - World Scientific.
Towards a stable definition of algorithmic randomness.Hector Zenil - unknown
Chance versus Randomness.Antony Eagle - 2010 - Stanford Encyclopedia of Philosophy.
Randomness and Semimeasures.Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter & Paul Shafer - 2017 - Notre Dame Journal of Formal Logic 58 (3):301-328.
Probabilistic algorithmic randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Quantum mechanics and algorithmic randomness.Ulvi Yurtsever - 2000 - Complexity 6 (1):27-34.
Exploring Randomness.Panu Raatikainen - 2001 - Notices of the AMS 48 (9):992-6.
How much randomness is needed for statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2012 - In S. Barry Cooper (ed.), Annals of Pure and Applied Logic. pp. 395--404.
How much randomness is needed for statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2014 - Annals of Pure and Applied Logic 165 (9):1470-1483.
Probability and Randomness.Antony Eagle - 2016 - In Alan Hájek & Christopher Hitchcock (eds.), The Oxford Handbook of Probability and Philosophy. Oxford: Oxford University Press. pp. 440-459.
Algorithmic randomness and complexity. Theory and Applications of Computability.Rodney G. Downey & Denis R. Hirschfeldt - 2012 - Bulletin of Symbolic Logic 18 (1):126-128.

Analytics

Added to PP
2019-04-25

Downloads
20 (#785,497)

6 months
9 (#349,017)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

B. R. George
University of California, Los Angeles (PhD)

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

Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
The K -Degrees, Low for K Degrees,and Weakly Low for K Sets.Joseph S. Miller - 2009 - Notre Dame Journal of Formal Logic 50 (4):381-391.

View all 21 references / Add more references