id: 05857621
dt: b
an: 05857621
au: Hölzl, Rupert
ti: Kolmogorov complexity.
so: Heidelberg: Univ. Heidelberg, Naturwissenschaftlich-Mathematische
    Gesamtfakultät. 98~p. (2010).
py: 2010
pu: Heidelberg: Univ. Heidelberg, Naturwissenschaftlich-Mathematische
    Gesamtfakultät
la: EN
cc: 
ut: Kolmogorov complexity without time bounds; non-monotonic randomness;
    randomness classes; traceability; time bounded Kolmogorov complexity;
    computational depth; Kummer’s gap theorem; Solovay functions;
    Martin-Loef randomness; jump-traceable
ci: 
li: http://archiv.ub.uni-heidelberg.de/volltextserver/frontdoor.php?source_opus=11446
ab: Summary: This dissertation discusses new results on Kolmogorov complexity.
    Its first part focuses on the study of Kolmogorov complexity without
    time bounds. Here we deal with the concept of non-monotonic randomness,
    that is, randomness characterized by martingales that bet
    non-monotonically. We will state the definitions of several different
    randomness classes and then separate them from each other. We also
    present a a systematic survey of a wide array of traceability notions
    and characterize them through (auto)complexity notions. Traceabilities
    are a group of notions that express that a set is not far away from
    being computable.  The second part of the document deals with the topic
    of time bounded Kolmogorov complexity. First we investigate the
    difference between two ways of describing a word: the complexity of
    describing it well enough so that it can be distinguished from other
    words, and the complexity of describing it well enough so that the word
    can actually be produced from the description. While this difference is
    unimportant in the case of Kolmogorov complexity without time bounds,
    it plays an essential role when time bounds are present. Next, we
    introduce the notion of computational depth and prove a dichotomy
    result about it that is reminiscent of Kummer’s well-known gap
    theorem. Lastly, we look at the important notion of Solovay functions.
    Solovay functions are computable upper bounds of Kolmogorov complexity
    that are actually sharp infinitely often. We will use them, first, to
    characterize Martin-Loef randomness in a certain way and, second, to
    give a characterization of being jump-traceable.
rv: