Probability Measures and Effective Randomness

arXiv0707.1390MaRDI QIDQ6206151FDOQ6206151

Theodore A. Slaman, Jan Reimann

Publication date: 10 July 2007

Abstract: We study the question, ``For which reals $x$ does there exist a measure $mu$ such that $x$ is random relative to $mu$? We show that for every nonrecursive $x$, there is a measure which makes $x$ random without concentrating on $x$. We give several conditions on $x$ equivalent to there being continuous measure which makes $x$ random. We show that for all but countably many reals $x$ these conditions apply, so there is a continuous measure which makes $x$ random. There is a meta-mathematical aspect of this investigation. As one requires higher arithmetic levels in the degree of randomness, one must make use of more iterates of the power set of the continuum to show that for all but countably many $x$'s there is a continuous $mu$ which makes $x$ random to that degree.

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Descriptive set theory (03E15) Applications of computability and recursion theory (03D80)

This page was built for publication: Probability Measures and Effective Randomness

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