Math 5026
Topics in Mathematical Logic
Spring 2013
This course is designed to give students a basic background in algorithmic randomness. We'll begin by studying basic computability theory: we'll formalize the concept of a computable function and what it means for one set of natural numbers to be computable from another set. This will give us the tools we'll need to study randomness for infinite binary sequences. We will talk about defining randomness using the unpredictability approach, the incompressibility approach, and the measure-theoretic approach. Then we will discuss the relationship between randomness and computational strength. While random sequences have a lot of information in them, that information cannot normally be retrieved in a computable way, so they may be (but need not be) computationally very weak.
No background in mathematical logic will be assumed.