Graduate Student Seminar, 4:00 pm October 9, 2006; HH229


Logan Axon



Effective Randomness for Fun and Profit



Generating a random binary sequence is as easy as flipping a coin. Do this infinitely often and you get an infinite binary sequence that is, in some sense, random. Suppose instead that you start with an infinite binary sequence and want to know if it is random. A probabilist might say, "All infinite binary sequences are equally (un) likely and so they're all random." This is kind of a boring answer. Fortunately computability theory comes to the rescue and provides an answer that is pretty interesting. I will introduce some of the central concepts of effective randomness along with all of the computability needed to understand these concepts.


To volunteer to give a talk, or for any other questions regarding this schedule, contact Sara Miller