80-618 Formal Methods: Algorithmic Randomness
6 units, Carnegie Mellon University
This course provides an introduction to algorithmic randomness an active branch of computability theory, according to which an individual mathematical object, such as a binary sequence, is random if it does not display any algorithmically predictable patterns. During the first part of the course, we will study the three main paradigms within which algorithmic randomness notions are defined the incompressibility paradigm, the measuretheoretic typicality paradigm, and the unpredictability paradigm. After discussing algorithmic randomness in the context of binary sequences, we will see that the theory can be generalized to the much broader setting of computable Polish spaces. In full generality, the theory of algorithmic randomness allows to specify what it means for an element of a probability space to be effectively typical and offers an account of what it means for a set to have effective measure zero. During the second part of the course, we will then focus on some recent applications of algorithmic randomness to the study of measure theory and analysis from a computabilitytheoretic perspective. In particular, we will see that, for many classical convergence theorems, algorithmic randomness can be used to provide a precise characterization of the points along which convergence occurs. We will conclude by discussing some of the philosophical ramifications of these results.
Prerequisites: none listed
Courseweave needs JavaScript to show sections, workloads and planning tools.