Computability Learning Seminar

Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo

“Algorithmic Randomness: Introduction to Kolmogorov Complexity”

The topic for the Computability Learning Seminar this term will be Algorithmic Random- ness. We will be following Nies’s book, Computability and Randomness.

In this talk, we begin in chapter two, which discusses the Descriptive Complexity (Kol- mogorov complexity) of strings. We are interested in ”descriptions” of strings, especially descriptions that are shorter than the given string itself. Indeed, we may be given a very long string of 0s and 1s but the characters appear in some ”easy” pattern that can be ”described” by a short string with few characters. We will be using binary strings to describe binary stings (To give some idea here, given a machine (mapping) M that takes strings and outputs strings, we will say that σ is an M-description of a string x if M(σ) = x). At the end we aim to have a rigorous definition for ”randomness” that fulfills the intuition why, for example, the infinite sequence (00000000....) is ”less random” than something like (01001110001000 ...).

MC 5403