Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Omega numbers, as considered in algorithmic randomness, are by definition real numbers that are equal to the halting probability of a universal prefix-free Turing machine. Omega numbers are obviously left-r.e., i.e., are effectively approximable from below. Furthermore, among all left-r.e. real numbers in the appropriate range between 0 and 1, the Omega numbers admit well-known characterizations as the ones that are Martin-Löf random, as well as the ones such that any of their effective approximation from below is slower than any other effective approximation from below to any other real, up to a constant factor. In what follows, we obtain a further characterization of Omega numbers in terms of Theta numbers.
Tadaki considered for a given prefix-free Turing machine and some natural number a the set of all strings that are compressed by this machine by at least a bits relative to their length, and he introduced Theta numbers as the weight of sets of this form.
He showed that in the case of a universal prefix-free Turing machine any Theta number is an Omega number and he asked whether this implication can be reversed. We answer his question in the affirmative and thus obtain a new characterization of Omega numbers.
In addition to the one-sided case of the set of all strings compressible by at least a certain number a of bits, we consider sets that comprise all strings that are compressible by at least a but no more than b bits, and we call the weight of such a set a two-sided Theta number. We demonstrate that in the case of a universal prefix-free Turing machine, for given a and all sufficiently large b the corresponding two-sided Theta number is again an Omega number. Conversely, any Omega number can be realized as two-sided Theta number for any pair of natural numbers a and b>a.

Wolfgang Merkle and Jason Teutsch. Constant compression and random weights. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 172-181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{merkle_et_al:LIPIcs.STACS.2012.172, author = {Merkle, Wolfgang and Teutsch, Jason}, title = {{Constant compression and random weights}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {172--181}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.172}, URN = {urn:nbn:de:0030-drops-34351}, doi = {10.4230/LIPIcs.STACS.2012.172}, annote = {Keywords: computational complexity, Kolmogorov complexity, algorithmic randomness, Omega number} }

Document

**Published in:** LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

As part of his groundbreaking work on algorithmic randomness, Solovay demonstrated in the 1970s the remarkable fact that there are computable upper bounds of prefix-free Kolmogorov complexity $K$ that are tight on infinitely many values (up to an additive constant). Such computable upper bounds are called Solovay functions. Recent work of Bienvenu and Downey~[STACS 2009, LIPIcs 3, pp 147-158] indicates that Solovay functions are deeply connected with central concepts of algorithmic randomness such as $Omega$ numbers, K-triviality, and Martin-Loef randomness.
In what follows, among other results we answer two open problems posed by Bienvenu and Downey about the definition of $K$-triviality and about the Gacs-Miller-Yu characterization of Martin-Loef randomness. The former defines a sequence A to be K-trivial if K(A|n) <=^+ K(n), the latter asserts that a sequence A is Martin-Loef random iff C(A|n) >=^+ n-K(n). So both involve the noncomputable function K. As our main results we show that in both cases K(n) can be equivalently replaced by any Solovay function, and, what is more, that among all computable functions such a replacement is possible exactly for the Solovay functions. Moreover, similar statements hold for the larger class of all right-c.e. in place of the computable functions. These full characterizations, besides having significant theoretical interest on their own, will be useful as tools when working with K-trivial and Martin-Loef random sequences.

Laurent Bienvenu, Wolfgang Merkle, and Andre Nies. Solovay functions and K-triviality. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 452-463, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2011.452, author = {Bienvenu, Laurent and Merkle, Wolfgang and Nies, Andre}, title = {{Solovay functions and K-triviality}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {452--463}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.452}, URN = {urn:nbn:de:0030-drops-30345}, doi = {10.4230/LIPIcs.STACS.2011.452}, annote = {Keywords: Algorithmic randomness, Kolmogorov complexity, K-triviality} }

Document

**Published in:** OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Martin-L\"of randomness
and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of Martin-L\"of randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural.
Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing non-monotonic strategies, i.e.\ strategies that do not bet on bits in order. The subsequent ``non-monotonic'' notion of randomness, now called Kolmogorov-Loveland-randomness, has been shown to be quite close to Martin-L\"of randomness, but whether these two classes coincide remains a fundamental open question.
In order to get a better understanding of non-monotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows non-adaptive strategies, i.e., strategies that can still bet non-monotonically, but such that the sequence of betting positions is known in advance (and computable). Recently, these notions were shown by Kastermans and Lempp to differ from Martin-L\"of randomness. We continue the study of the non-monotonic randomness notions introduced by Miller and Nies and obtain results about the Kolmogorov complexities of initial segments that may and may not occur for such sequences, where these results then imply a complete classification of these randomness notions by order of strength.

Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle. Separations of Non-monotonic Randomness Notions. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:OASIcs.CCA.2009.2260, author = {Bienvenu, Laurent and H\"{o}lzl, Rupert and Kr\"{a}ling, Thorsten and Merkle, Wolfgang}, title = {{Separations of Non-monotonic Randomness Notions}}, booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)}, pages = {71--82}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-12-5}, ISSN = {2190-6807}, year = {2009}, volume = {11}, editor = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2260}, URN = {urn:nbn:de:0030-drops-22601}, doi = {10.4230/OASIcs.CCA.2009.2260}, annote = {Keywords: Martin-L\"{o}f randomness, Kolmogorov-Loveland randomness, Kolmogorov complexity, martingales, betting strategies} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

From 29.01.06 to 03.02.06, the Dagstuhl Seminar 06051 ``Kolmogorov Complexity and Applications'' was held in the International Conference and Research Center (IBFI),
Schloss Dagstuhl. During the seminar, several participants presented
their current research, and ongoing work and open problems were
discussed. Abstracts of the presentations given during the seminar
as well as abstracts of seminar results and ideas are put together
in this paper. The first section describes the seminar topics and
goals in general. Links to extended abstracts or full papers are
provided, if available.

Marcus Hutter, Wolfgang Merkle, and Paul M.B. Vitanyi. 06051 Abstracts Collection – Kolmogorov Complexity and Applications. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{hutter_et_al:DagSemProc.06051.1, author = {Hutter, Marcus and Merkle, Wolfgang and Vitanyi, Paul M.B.}, title = {{06051 Abstracts Collection – Kolmogorov Complexity and Applications}}, booktitle = {Kolmogorov Complexity and Applications}, pages = {1--17}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6051}, editor = {Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.1}, URN = {urn:nbn:de:0030-drops-6632}, doi = {10.4230/DagSemProc.06051.1}, annote = {Keywords: Information theory, Kolmogorov Complexity, effective randomnes, algorithmic probability, recursion theory, computational complexity, machine learning knowledge discovery} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi. Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181). Dagstuhl Seminar Report 377, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{durand_et_al:DagSemRep.377, author = {Durand, Bruno and Levin, Leonid A. and Merkle, Wolfgang and Shen, Alexander and Vitanyi, Paul M. B.}, title = {{Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)}}, pages = {1--6}, ISSN = {1619-0203}, year = {2003}, type = {Dagstuhl Seminar Report}, number = {377}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.377}, URN = {urn:nbn:de:0030-drops-152578}, doi = {10.4230/DagSemRep.377}, }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail