Event Detail

Event Type: 
Graduate Student Summer Seminar
Wednesday, July 27, 2016 - 14:30 to 15:30
KIdder 364

Kolmogorov complexity gives us a way to quantify our intuitive notion of the complexity of finite bit strings up to an additive constant. For arbitrarily long strings this quantity becomes an absolute measure of the string’s complexity.

I will discuss the history of Kolmogorov Complexity and a more applicable notion known as Computable Randomness. I will also attempt to briefly summarize a question which asks whether there is an equivalence in the hierarchy of sets when ranked by their ability to determine the Computable Randomness of bit sequences, with those ranked by their ability to determine the contents of each other when viewed as information oracles for Turing Machines.