Numberings and randomness

DOI10.1007/978-3-642-03073-4_6MaRDI QIDQ3576037zbMATH OpenOpenAlexFDO

Authors Paul Brodhead, Bjørn Kjos-Hanssen

Publication date 28 July 2010

Published in Mathematical Theory and Computational Practice (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2169

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Theory of numerations, effectively presented structures (03D45)

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 $P{i}_1^0$ classes of positive measure. On the other hand, the $P{i}_1^0$ 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 $P{i}_1^0$ classes contained in the class of reals satisfying a fixed randomness constant, we prove that at least an effective numbering exists.

Recommendations

• Arithmetic complexity via effective names for random sequences
• scientific article; zbMATH DE number 2167508
• Computable numberings of families of infinite sets
• The Kolmogorov complexity of random reals
• Some results on effective randomness

Cites work

• An easy priority-free proof of a theorem of Friedberg
• An extension of the recursively enumerable Turing degrees
• Computability and Randomness
• Effectively closed sets and enumerations
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1390024 (Why is no real title available?)
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication

Cited in

(11)

• Precomplete numberings
• Things that can be made into themselves
• Reductions between types of numberings
• Arithmetic complexity via effective names for random sequences
• scientific article; zbMATH DE number 5252382 (Why is no real title available?)
• Effectively infinite classes of numberings of computable families of reals
• Effectively infinite classes of numberings and computable families of reals
• Computable operators on left-c.e. reals and their continuity properties
• On infinite direct sums of minimal numberings of functional families
• Continuity theorems for a class of computable operators
• Computably enumerable sets of reals in constructive mathematical analysis

This page was built for publication: Numberings and randomness

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