Randomness for computable measures and initial segment complexity

DOI10.1016/J.APAL.2016.10.014MaRDI QIDQ508835zbMATH OpenOpenAlexFDO

Authors Rupert Hölzl, Christopher P. Porter

Publication date 8 February 2017

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

random sequencesatomic measurescomplex sequencescomputable measuresdiminutive measurestrivial measures

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32)

Abstract: We study the possible growth rates of the Kolmogorov complexity of initial segments of sequences that are random with respect to some computable measure on $2^{o}mega$, the so-called proper sequences. Our main results are as follows: (1) We show that the initial segment complexity of a proper sequence $X$ is bounded from below by a computable function (that is, $X$ is complex) if and only if $X$ is random with respect to some computable, continuous measure. (2) We prove that a uniform version of the previous result fails to hold: there is a family of complex sequences that are random with respect to a single computable measure such that for every computable, continuous measure $mu$, some sequence in this family fails to be random with respect to $mu$. (3) We show that there are proper sequences with extremely slow-growing initial segment complexity, that is, there is a proper sequence the initial segment complexity of which is infinitely often below every computable function, and even a proper sequence the initial segment complexity of which is dominated by all computable functions. (4) We prove various facts about the Turing degrees of such sequences and show that they are useful in the study of certain classes of pathological measures on $2^{o}mega$, namely diminutive measures and trivial measures.

Recommendations

• Randomness and initial segment complexity for measures
• Mass problems and initial segment complexity
• The Kolmogorov complexity of random reals
• The complexity of stochastic sequences
• On initial segment complexity and degrees of randomness

Cites work

• scientific article; zbMATH DE number 4051595 (Why is no real title available?)
• scientific article; zbMATH DE number 4068853 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3489017 (Why is no real title available?)
• scientific article; zbMATH DE number 3402606 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic randomness and complexity.
• Anti-complex sets and reducibilities with tiny use
• Computability and randomness
• Computational aspects of the hyperimmune-free degrees
• Demuth's path to randomness
• Effectively closed sets of measures and randomness
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Kolmogorov complexity and solovay functions
• Measures and their random reals
• On effectively closed sets of effective strong measure zero
• Propagation of partial randomness
• 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
• Traceable Sets
• Trivial measures are not so trivial
• \(K\)-trivials are never continuously random
• Π₁⁰ classes with complex elements

Cited in

(15)

• Randomness and initial segment complexity for measures
• On trees without hyperimmune branches
• Rank and randomness
• Resolute sequences in initial segment complexity
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Initial segment complexities of randomness notions
• On process complexity
• Sub-computable Boundedness Randomness
• Descriptive complexity of computable sequences
• Mass problems and initial segment complexity
• Computable Measure Theory and Algorithmic Randomness
• The complexity of stochastic sequences
• Shift-complex sequences
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• On elementary computability-theoretic properties of algorithmic randomness

This page was built for publication: Randomness for computable measures and initial segment complexity

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