Seminar on Topics in Logic: Algorithmic Randomness

Catalog description

What is randomness? One way to think about it is as a property of sequences of, say, events, experimental outcomes, observations, or symbols from some alphabet: a sequence is random if it is unruly, irregular, patternless. This conception of randomness plays a significant role in a variety of fields, including cryptography, information theory, the foundations of probability and statistics, computability theory, and certain computational models of learning. To build some intuition, consider the two binary strings 0010111110 and 0101010101. The first string seems more random-looking than the second. This is because the second string displays an obvious pattern that is very easy to describe and that makes it look highly predictable. But can these intuitions be made precise? Is it possible to provide a rigorous mathematical characterization of the notion of a random sequence? This seminar will provide an introduction to the theory of algorithmic randomnessan active branch of computability theoryaccording to which a sequence is random if it does not display any algorithmically detectable patterns. We will begin by discussing von Mises' theory of collectives, a precursor to the theory of algorithmic randomness; then, we will see how von Mises' work led to the modern computability-theoretic approach to randomness. We will focus on both the mathematical details of the theory of algorithmic randomness and its philosophical consequences. We will pay special attention to the connections between randomness, probability, and the philosophical interpretations of probability. Among the questions that we will address are: What is the relationship between probability and randomness? Is probability more primitive a concept than randomness, or is a precise analysis of randomness needed to understand what probabilities are? Is it possible to define "absolute" randomness? Does randomness…