Randomness for computable measures and initial segment complexity

DOI10.1016/J.APAL.2016.10.014zbMATH Open1404.03039arXiv1510.07202OpenAlexW1823933177MaRDI QIDQ508835FDOQ508835

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)

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.

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

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

zbMATH Keywords

random sequencesatomic measurescomplex sequencescomputable measuresdiminutive measurestrivial measures

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32)

Cites Work

• Algorithmic randomness and complexity.
• Computability and randomness
• Title not available (Why is that?)
• A Theory of Program Size Formally Identical to Information Theory
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Traceable Sets
• Title not available (Why is that?)
• Strong reductions in effective randomness
• Kolmogorov complexity and solovay functions
• Propagation of partial randomness
• Π₁⁰ classes with complex elements
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Effectively closed sets of measures and randomness
• Title not available (Why is that?)
• Trivial measures are not so trivial
• On effectively closed sets of effective strong measure zero
• Demuth's path to randomness
• Title not available (Why is that?)
• \(K\)-trivials are never continuously random
• Measures and their random reals
• Anti-complex sets and reducibilities with tiny use
• Title not available (Why is that?)
• Computational aspects of the hyperimmune-free degrees

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)