On the construction of effectively random sets

Journal of Symbolic Logic 69 (3):862-878 (2004)
  Copy   BIBTEX

Abstract

We present a comparatively simple way to construct Martin-Löf random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of Gács and Kučera, for any given set X we construct a Martin-Löf random set from which X can be decoded effectively. By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-Löf random sets that are computably enumerable self-reducible. The two latter results complement the known facts that no rec-random set is truth-table autoreducible and that no Martin-Löf random set is Turing-autoreducible [8, 24]

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,221

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

Relative Randomness and Cardinality.George Barmpalias - 2010 - Notre Dame Journal of Formal Logic 51 (2):195-205.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Computational randomness and lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
Lowness for the class of random sets.Antonín Kučera & Sebastiaan A. Terwijn - 1999 - Journal of Symbolic Logic 64 (4):1396-1402.
Subclasses of the Weakly Random Reals.Johanna N. Y. Franklin - 2010 - Notre Dame Journal of Formal Logic 51 (4):417-426.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.

Analytics

Added to PP
2009-02-05

Downloads
216 (#84,759)

6 months
3 (#439,232)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.

Add more citations

References found in this work

Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.

Add more references