Randomness and computability: Open questions

Bulletin of Symbolic Logic 12 (3):390-410 (2006)
  Copy   BIBTEX

Abstract

It is time for a new paper about open questions in the currently very active area of randomness and computability. Ambos-Spies and Kučera presented such a paper in 1999 [1]. All the question in it have been solved, except for one: is KL-randomness different from Martin-Löf randomness? This question is discussed in Section 6.Not all the questions are necessarily hard—some simply have not been tried seriously. When we think a question is a major one, and therefore likely to be hard, we indicate this by the symbol ▶, the criterion being that it is of considerable interest and has been tried by a number of researchers. Some questions are close contenders here; these are marked by ▷. With few exceptions, the questions are precise. They mostly have a yes/no answer. However, there are often more general questions of an intuitive or even philosophical nature behind. We give an outline, indicating the more general questions.All sets will be sets of natural numbers, unless otherwise stated. These sets are identified with infinite strings over {0, 1}. Other terms used in the literature are sequence and real.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,551

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

Computability and Randomness.André Nies - 2009 - Oxford University Press.
Defining a randomness notion via another.Kojiro Higuchi & Ningning Peng - 2014 - Mathematical Logic Quarterly 60 (4-5):280-288.
Computable randomness and betting for computable probability spaces.Jason Rute - 2016 - Mathematical Logic Quarterly 62 (4-5):335-366.
Computational randomness and lowness.Sebastiaan Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Indifferent sets for genericity.Adam R. Day - 2013 - Journal of Symbolic Logic 78 (1):113-138.
Algorithmic randomness over general spaces.Kenshi Miyabe - 2014 - Mathematical Logic Quarterly 60 (3):184-204.

Analytics

Added to PP
2009-01-28

Downloads
102 (#208,185)

6 months
18 (#164,932)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Benign cost functions and lowness properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
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.
Denjoy, Demuth and density.Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies - 2014 - Journal of Mathematical Logic 14 (1):1450004.

View all 19 citations / Add more citations

References found in this work

Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Computational randomness and lowness.Sebastiaan Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
The axiomatization of randomness.Michiel van Lambalgen - 1990 - Journal of Symbolic Logic 55 (3):1143-1167.
Lowness for genericity.Liang Yu - 2006 - Archive for Mathematical Logic 45 (2):233-238.

View all 16 references / Add more references