Date: Monday, April 20, 2015
Title: Defining randomness algorithmically
Abstract: When shown a binary sequence, most people can intuitively describe it as “random” or “not random.” However, as mathematicians, we want a precise mathematical definition of randomness. In this talk, I will characterize randomness with concepts from computability theory using three different intuitive approaches as starting points: unpredictability, incompressibility, and a lack of distinguishing properties. If time permits, I will discuss different formalizations within each approach that result in different kinds of randomness and how well these formalizations fit our intuitions about other properties a random sequence should have.