Solovay functions and their applications in algorithmic randomness

DOI10.1016/J.JCSS.2015.04.004zbMATH Open1335.03038arXiv1603.08351OpenAlexW315655538MaRDI QIDQ494057FDOQ494057

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)

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.

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

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

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)

Cites Work

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

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)