Turing degrees and randomness for continuous measures

DOI10.1007/S00153-023-00873-7MaRDI QIDQ6178468zbMATH OpenOpenAlexFDO

Authors Mingyang Li, Jan Reimann

Publication date 18 January 2024

Published in Archive for Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic randomnesscontinuous measuresmoduli of computationrecursively enumerable and aboveTuring degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Abstract: We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a family of generalized Hausdorff measures based on the iterates of the "dissipation" function of a continuous measure and study the effective nullsets given by the corresponding Solovay tests. We introduce two constructions that preserve non-randomness with respect to a given continuous measure. This enables us to prove the existence of NCR reals in a number of Turing degrees. In particular, we show that every $Delt{a}_2^0$-degree contains an NCR element.

Review text

A real is never continuous random (NCR for short) if it is not random with respect to any continuous measure. This notion has been studied by a number of people. But it is still unknown which Turing degree can contain such reals. In the paper under review, the authors prove some nice results to make some contributions to the topic. The major results are that any \(n\)-REA Turing degree contains an NCR real; and any selfmodule Turing degree contains an NCR real.

Recommendations

• Measures and their random reals
• Randomness for non-computable measures
• The typical Turing degree
• \(K\)-trivials are never continuously random
• Effective randomness for continuous measures

Cites work

• \(K\)-trivials are never continuously random
• Algorithmic randomness and complexity.
• Computability and Randomness
• Effective randomness for continuous measures
• Effectively closed sets of measures and randomness
• scientific article; zbMATH DE number 3532844 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• Measures and their random reals
• Members of countable \(\Pi ^ 0_ 1\) classes
• Randomness for non-computable measures
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• Turing computability. Theory and applications

Cited in

(1)

• Effective randomness for continuous measures

This page was built for publication: Turing degrees and randomness for continuous measures

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