pith. sign in

arxiv: 1408.2169 · v1 · pith:FAL7AFG3new · submitted 2014-08-10 · 🧮 math.LO

Numberings and randomness

classification 🧮 math.LO
keywords randomnessrealsclasseseffectivenumberingnumberingsconstantcontained
0
0 comments X
read the original abstract

We prove various results on effective numberings and Friedberg numberings of families related to algorithmic randomness. The family of all Martin-L\"of random left-computably enumerable reals has a Friedberg numbering, as does the family of all $\Pi^0_1$ classes of positive measure. On the other hand, the $\Pi^0_1$ classes contained in the Martin-L\"of random reals do not even have an effective numbering, nor do the left-c.e. reals satisfying a fixed randomness constant. For $\Pi^0_1$ classes contained in the class of reals satisfying a fixed randomness constant, we prove that at least an effective numbering exists.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.