Solovay functions and their applications in algorithmic randomness

DOI10.1016/j.jcss.2015.04.004zbMath1335.03038arXiv1603.08351OpenAlexW315655538MaRDI QIDQ494057

Laurent Bienvenu, Wolfgang Merkle, André Nies, 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 information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (4)

Coherence of reducibilities with randomness notions ⋮ Searching for shortest and least programs ⋮ BEING LOW ALONG A SEQUENCE AND ELSEWHERE ⋮ SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oscillation in the initial segment complexity of random reals
• On the number of infinite sequences with trivial initial segment complexity
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Incompleteness theorems for random reals
• Information-theoretic characterizations of recursive infinite strings
• Time-bounded Kolmogorov complexity and Solovay functions
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Process complexity and effective random tests
• Lowness properties and randomness
• Kolmogorov-Loveland randomness and stochasticity
• Randomness and Recursive Enumerability
• $K$-triviality in computable metric spaces
• Random Semicomputable Reals Revisited
• COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS
• The Surprise Examination Paradox and the Second Incompleteness Theorem
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• A minimal pair of 𝐾-degrees
• On initial segment complexity and degrees of randomness
• Clustering by Compression
• Every sequence is reducible to a random one
• Exact Expressions for Some Randomness Tests
• A Theory of Program Size Formally Identical to Information Theory
• On the construction of effectively random sets
• Kolmogorov Complexity and Solovay Functions
• An introduction to Kolmogorov complexity and its applications

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