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

atomic measurescomplex sequencescomputable measuresdiminutive measuresrandom sequencestrivial 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.

Review text

The paper studies the growth rates of the Kolmogorov complexity of initial segments of proper sequences, i.e. sequences that are random with respect to some computable measure on \(2^{\omega}\). There are four main results: {\parindent=7mm \begin{itemize}\item[(1)] the initial segment complexity of a proper sequence \(X\) is bounded from below by a computable function iff \(X\) is random with respect to some computable, continuous measure; \item[(2)] 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\); \item[(3)] there are proper sequences with extremely slow-growing initial segment complexity; \item[(4)] various facts about the Turing degrees of proper sequences. \end{itemize}} All results are properly explained and proved in detail.

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

• \(K\)-trivials are never continuously random
• 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
• 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?)
• 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
• Π₁⁰ classes with complex elements

Cited in

(17)

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

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)