Kolmogorov Complexity and Solovay Functions

Bienvenu, Laurent; Downey, Rod

doi:10.4230/LIPIcs.STACS.2009.1810

Document

Kolmogorov Complexity and Solovay Functions

Authors Laurent Bienvenu, Rod Downey

Part of: Volume: 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NoDerivs 3.0 Unported license
Publication Date: 2009-02-19

PDF

File

PDF

LIPIcs.STACS.2009.1810.pdf

Filesize: 182 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2009.1810
URN: urn:nbn:de:0030-drops-18107

Subject Classification

Keywords

Algorithmic randomness
Kolmogorov complexity
K-triviality

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

Solovay (1975) proved that there exists a computable upper bound~$f$ of the prefix-free Kolmogorov complexity function~$K$ such that $f(x)=K(x)$ for infinitely many~$x$. In this paper, we consider the class of computable functions~$f$ such that $K(x) \leq f(x)+O(1)$ for all~$x$ and $f(x) \leq K(x)+O(1)$ for infinitely many~$x$, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality.

Cite As Get BibTex

Laurent Bienvenu and Rod Downey. Kolmogorov Complexity and Solovay Functions. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 147-158, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1810

Author Details

Laurent Bienvenu

Rod Downey

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail