Randomness for non-computable measures
The theory of algorithmic randomness for computable measures on Cantor space is well-developed. However, if \(\mu\) is a noncomputable measure then it stands to reason that when designating an effective \(\mu\)-null set we should have access to \(\mu\). A complication arises when \(\mu\) does not have a Turing degree but merely a continuous degree. The authors show that two definitions for \(\mu\)-randomness -- using representations of the measure which have Turing degree, or using uniform ``integral tests -- are equivalent. We thus get a robust notion of \(\mu\)-randomness for all measures~\(\mu\), computable or not.NEWLINENEWLINEThis theory is then used to better understand Levin's ``neutral measure, a measure relative to which every sequence is random. The authors use Kakutani's fixed-point theorem to construct such a measure. They also conclude that every PA-complete Turing degree computes a neutral measure; this gives a quick proof of a result by \textit{J. Reimann} and \textit{T. A. Slaman} [``Measures and their random reals, Preprint, \url{arXiv:0802.2705}], that a sequence is noncomputable if and only if it is random relative to a measure of which it is not an atom. In fact, the ideals of total degrees below the continuous degrees of neutral measures are precisely the countable Scott sets.NEWLINENEWLINEIn later work [Notre Dame J. Formal Logic 55, No. 1, 1--10 (2014; Zbl 1332.03010)], the first author and \textit{J. Reimann} further investigate relative randomness and obtain further results concerning PA degrees.
- Trivial measures are not so trivial
- Measures and their random reals
- scientific article; zbMATH DE number 7650940
- On relative randomness
- Randomness -- beyond Lebesgue measure
- Constructive equivalence relations on computable probability measures
- Degrees of randomized computability
- scientific article; zbMATH DE number 5264766
- scientific article; zbMATH DE number 3559552
- Computable Measure Theory and Algorithmic Randomness
- A generalization of Brouwer's fixed point theorem
- Algorithmic randomness and complexity.
- Arithmetical Reducibilities I
- Computability and randomness
- Computability of probability measures and Martin-Löf randomness over metric spaces
- Degrees of unsolvability of continuous functions
- Effectively closed sets of measures and randomness
- scientific article; zbMATH DE number 1354815 (Why is no real title available?)
- scientific article; zbMATH DE number 1460545 (Why is no real title available?)
- Measures and their random reals
- On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
- 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
- Uniform test of algorithmic randomness over a general space
- ∏ 0 1 Classes and Degrees of Theories
- Energy randomness
- Schnorr randomness for noncomputable measures
- Martin-Löf random generalized Poisson processes
- Equivalences between learning of data and probability distributions, and their applications
- The random members of a \({\Pi }_{1}^{0}\) class
- Randomness and initial segment complexity for measures
- Characterizing the continuous degrees
- Cone avoidance and randomness preservation
- Independence, relative randomness, and PA degrees
- Algorithmic tests and randomness with respect to a class of measures
- Randomness -- beyond Lebesgue measure
- Measure, randomness and sublocales
- Random sequences with respect to a measure defined by two linear fractional transformations
- Computability of Subsets of Metric Spaces
- Universal coding and prediction on ergodic random points
- Degrees of randomized computability
- A structural dichotomy in the enumeration degrees
- On a metric generalization of the \(tt\)-degrees and effective dimension theory
- Measures and their random reals
- Martin-Löf randomness in spaces of closed sets
- Effective randomness for continuous measures
- Point Degree Spectra of Represented Spaces
- Continuous randomness via transformations of 2-random sequences
- COMPUTABLY COMPACT METRIC SPACES
- Turing degrees and randomness for continuous measures
- Mass problems associated with effectively closed sets
This page was built for publication: Randomness for non-computable measures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2846975)
