# Meeting Details

Title: Initial segment complexity and randomness for computable measures Logic Seminar Christopher P. Porter, University of Florida According to the Levin-Schnorr theorem, a sequence $X$ is Martin-Löf random with respect to the Lebesgue measure if and only if $K(X\upharpoonright n)\geq n-O(1)$ for every $n$, where $K$ denotes prefix-free Kolmogorov complexity. It is well-known that this theorem can be extended to proper sequences, that is, sequences that are random with respect to some computable measure. Nonetheless, one can show that there are proper sequences with slow-growing initial segment complexity (i.e., there is no computable lower bound for their initial segment complexity). I will discuss joint work with Rupert Hölzl and Wolfgang Merkle in which we study the various growth rates of the initial segment complexity of proper sequences.