HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Kolmogorov Complexity and Solovay Functions

Abstract : Solovay 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) ≤ f (x)+O(1) for all x and f (x) ≤ 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öf randomness and K-triviality.
Complete list of metadata

https://hal.inria.fr/inria-00359056
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, February 5, 2009 - 2:27:58 PM
Last modification on : Monday, January 18, 2021 - 11:50:32 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:14:03 PM

Files

bienvenu_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00359056, version 1
  • ARXIV : 0902.1041

Collections

Citation

Laurent Bienvenu, Rodney Downey. Kolmogorov Complexity and Solovay Functions. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.147-158. ⟨inria-00359056⟩

Share

Metrics

Record views

50

Files downloads

149