PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson, Jason Rute, Jan Reimann.

Title:Initial segment complexity and randomness for computable measures
Seminar:Logic Seminar
Speaker: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.

Room Reservation Information

Room Number:MB315
Date:02 / 10 / 2015
Time:02:30pm - 03:45pm