Some questions of uniformity in algorithmic randomness

Journal of Symbolic Logic 86 (4):1612-1631 (2021)
  Copy   BIBTEX


The $\Omega $ numbers—the halting probabilities of universal prefix-free machines—are known to be exactly the Martin-Löf random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-Löf random left-c.e. real $\alpha $, a universal prefix-free machine U whose halting probability is $\alpha $. We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real $\alpha $, one cannot uniformly produce a left-c.e. real $\beta $ such that $\alpha - \beta $ is neither left-c.e. nor right-c.e.



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

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

Levels of Uniformity.Rutger Kuyper - 2019 - Notre Dame Journal of Formal Logic 60 (1):119-138.
Randomness and Semimeasures.Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter & Paul Shafer - 2017 - Notre Dame Journal of Formal Logic 58 (3):301-328.
Demuth’s path to randomness.Antonín Kučera, André Nies & Christopher P. Porter - 2015 - Bulletin of Symbolic Logic 21 (3):270-305.
Probabilistic algorithmic randomness.Sam Buss & Mia Minnes - 2013 - Journal of Symbolic Logic 78 (2):579-601.
Algorithmic randomness and measures of complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
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.
Schnorr randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533-554.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.


Added to PP

8 (#1,324,279)

6 months
7 (#441,061)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references