Some Questions of Uniformity in Algorithmic Randomness

DOI10.1017/JSL.2021.58MaRDI QIDQ6381940arXivFDO

Authors Laurent Bienvenu, Barbara Csima, Matthew Harrison-Trainor

Publication date 2 November 2021

Published in arXiv

Full work available at URL https://doi.org/10.1017/JSL.2021.58

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32)

arXiv classification

cs.LOmath.LO

Abstract: The $Omega$ numbers-the halting probabilities of universal prefix-free machines-are known to be exactly the Martin-L{"o}f random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-L{"o}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 $$ such that $alpha$ -- $$ is neither left-c.e. nor right-c.e.

This page was built for publication: Some Questions of Uniformity in Algorithmic Randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6381940)