Solovay functions and their applications in algorithmic randomness

DOI10.1016/J.JCSS.2015.04.004MaRDI QIDQ494057zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, André Nies, Wolfgang Merkle, Rodney G. Downey

Publication date 31 August 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexityalgorithmic randomness\(K\)-trivial sequences, \(c\)-hitting setsSolovay functions

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: Classical versions of Kolmogorov complexity are incomputable. Nevertheless, in 1975 Solovay showed that there are computable functions $f>K+O(1)$ such that for infinitely many strings $sigma$, $f(sigma)=K(sigma)+O(1)$, where $K$ denotes prefix-free Kolmogorov complexity (while $C$ denotes plain Kolmogorov complexity). Such an $f$ is now called a Solovay function. We prove that many classical results about $K$ can be obtained by replacing $K$ by a Solovay function. For example, the three following properties of a function $g$ all hold for the function $K$. (i) The sum of the terms $su{m}_n{2}^{-g(n)}$ is a Martin-L"of random real. (ii) A sequence A is Martin-L"of random if and only if $C(Aupharpoonrightn)>n-g(n)-O(1)$. (iii) A sequence A is K-trivial if and only if $K(Aupharpoonrightn)<g(n)+O(1)$. We show that when fixing any of these three properties, then among all computable functions exactly the Solovay functions possess this property. Furthermore, this characterization extends accordingly to the larger class of right-c.e. functions.

Recommendations

• Randomness and Solovay degrees
• Algorithmic randomness of continuous functions
• Algorithmically Random Functions and Effective Capacities
• Kolmogorov complexity and solovay functions
• Algorithmic randomness and Fourier analysis
• scientific article; zbMATH DE number 3942641
• Randomized algorithms in number theory
• Publication:3484822
• Pseudorandom functions and lattices
• Number-theoretic constructions of efficient pseudo-random functions

Cites work

• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A minimal pair of 𝐾-degrees
• Algorithmic randomness and complexity.
• An introduction to Kolmogorov complexity and its applications
• Clustering by Compression
• Computability and randomness
• Computuing \(K\)-trivial sets by incomplete random sets
• Every sequence is reducible to a random one
• Exact Expressions for Some Randomness Tests
• Incompleteness theorems for random reals
• Information-theoretic characterizations of recursive infinite strings
• Kolmogorov complexity and solovay functions
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• Kolmogorov-Loveland randomness and stochasticity
• Lowness properties and randomness
• On initial segment complexity and degrees of randomness
• On the construction of effectively random sets
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• On the number of infinite sequences with trivial initial segment complexity
• Oscillation in the initial segment complexity of random reals
• Process complexity and effective random tests
• Random semicomputable reals revisited
• Randomness and recursive enumerability
• Solovay functions and \(K\)-triviality
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• The surprise examination paradox and the second incompleteness theorem
• Time-bounded Kolmogorov complexity and Solovay functions
• \(K\)-triviality in computable metric spaces

Cited in

(10)

• Time-bounded Kolmogorov complexity and Solovay functions
• Calculus of cost functions
• Kolmogorov complexity and solovay functions
• Algorithmically Random Functions and Effective Capacities
• Solovay functions and \(K\)-triviality
• Being low along a sequence and elsewhere
• SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS
• Coherence of reducibilities with randomness notions
• Searching for shortest and least programs
• Time-Bounded Kolmogorov Complexity and Solovay Functions

This page was built for publication: Solovay functions and their applications in algorithmic randomness

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