UC Berkeley

The prefix-free Kolmogorov complexity, K(σ), of a finite binary string σ is the length of the shortest self-delimiting program that outputs σ and is a measure of the information content of σ. There are two very natural ways to extend this notion to infinite binary strings (identified as the binary expansions of real numbers in the interval [0,1]): one can examine the initial segment complexity of a real, i.e. K(A|n)$ as a function of n, or one can examine the compressive power of A as an oracle, i.e. K^A(σ) as a function of σ.

Each of these approaches has a notion of minimality for reals. A real is K-trivial if the complexities of its initial segments are up to a constant just the complexities of their lengths. A real is low for K if it provides no more than an additive constant advantage to compressing any string.

This dissertation examines weakenings of these notions that arise from replacing the constant bounds with slow-growing functions. The main results are that these weaker lowness notions behave very differently from the standard ones in terms of the sets of reals defined by these notions. We also include applications of these new notions to effective dimension and mutual information.