Numberings and randomness

Abstract

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

Identifiers

DOI

10.48550/arxiv.1408.2169

Citations and references