## Contact Info

Pure MathematicsUniversity of Waterloo

200 University Avenue West

Waterloo, Ontario, Canada

N2L 3G1

Departmental office: MC 5304

Phone: 519 888 4567 x33484

Fax: 519 725 0160

Email: puremath@uwaterloo.ca

Wednesday, September 16, 2015 — 3:30 PM EDT

**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

University of Waterloo

200 University Avenue West

Waterloo, Ontario, Canada

N2L 3G1

Departmental office: MC 5304

Phone: 519 888 4567 x33484

Fax: 519 725 0160

Email: puremath@uwaterloo.ca

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1