Graduate Students
Graduate Programs     
Graduate Home Ph D Programs Masters Degree Ph D Program Requirements Course Descriptions Current Courses Admissions Current Graduate Students Graduate Student Seminar SIAM Chapter Seminar Recent Graduates Incoming Students

Apply Now
Graduate Seminar

Jason Rute
Carnegie Melllon University
Title: Randomness and Computable Analysis

Abstract: Probabilists often work with various infinite processes. One of the easiest processes to understand is a fair coin that is flipped infinitely often. While one would expect such a sequence of flips to have certain properties---such as an (asymptotically) equal number of 0's (tails) and 1's (heads)---there are obvious counterexamples, for example the string of all tails (000...). Such counterexamples are somehow not "random" enough.

One could naively define a "random" string as one which avoids all probability zero events, but such a definition is quickly seen to be vacuous. Instead, if we limit ourselves to "computable" probability zero events, such a definition is not only consistent, but also interesting and robust.

In this talk I will talk about the basics of computable analysis, and at the end use it to define a type of algorithmic randomness called Martin-Lof randomness.

Computable analysis is not just a means to an end; it is itself an interesting field that makes precise the computational concerns of much of modern and classical mathematics. As an example, I will give a computation interpretation of the notions of point, open set, continuous function, and null set in a variety of well known spaces.

If time allows, I will then talk about some of the properties of Martin-Lof random sequences.

Date: Tuesday, January 18, 2011
Time: 6:00 pm
Location: Wean Hall 8220
Submitted by:  Chris Almost