Rank and randomness

DOI10.1017/JSL.2019.65MaRDI QIDQ5207564zbMATH OpenOpenAlexFDO

Authors Rupert Hölzl, Christopher P. Porter

Publication date 10 January 2020

Published in Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic randomnessCantor-Bendixson rankcomputable measuresMartin-Löf randomness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We show that for each computable ordinal $alpha>0$ it is possible to find in each Martin-L"of random $Delt{a}_2^0$ degree a sequence $R$ of Cantor-Bendixson rank $alpha$, while ensuring that the sequences that inductively witness $R$'s rank are all Martin-L"of random with respect to a single countably supported and computable measure. This is a strengthening for random degrees of a recent result of Downey, Wu, and Yang, and can be understood as a randomized version of it.

Recommendations

• scientific article; zbMATH DE number 1531917
• Randomness, lowness and degrees
• Lowness for the class of random sets
• Randomness and the linear degrees of computability
• On partial randomness

Cites work

• Classical recursion theory. Vol. II
• Computable structures and the hyperarithmetical hierarchy
• scientific article; zbMATH DE number 3151582 (Why is no real title available?)
• scientific article; zbMATH DE number 1390012 (Why is no real title available?)
• Index sets for ^0_1 classes
• On the Cantor-Bendixon rank of recursively enumerable sets
• On the ranked points of a Π₁⁰ set
• Randomness for computable measures and initial segment complexity
• Rank, join, and Cantor singletons
• Strong reductions in effective randomness
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The members of thin and minimal \(\Pi_1^0\) classes, their ranks and Turing degrees
• Trivial measures are not so trivial
• Π₁⁰ classes with complex elements

Cited in

(1)

• Measures and their random reals

This page was built for publication: Rank and randomness

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