80-817 Seminar on Topics in Logic: Algorithmic Randomness
12 units, Carnegie Mellon University
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. This seminar will provide an introduction to the theory of algorithmic randomnessan active branch of computability theory according 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 computabilitytheoretic 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 various philosophical interpretations of probability. Among the questions that we will address are What is the relationship between probability and randomness Is it possible to reduce one concept to the other Is probability more primitive a concept than randomness, or, vice versa, is a precise analysis of the concept of randomness needed to understand what probabilities are Is it possible to define absolute randomness Does randomness have to satisfy any laws
Prerequisites: none listed
Courseweave needs JavaScript to show sections, workloads and planning tools.