Computability Learning SeminarExport this event to calendar

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

S M T W T F S
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
  1. 2019 (182)
    1. November (16)
    2. October (19)
    3. September (13)
    4. August (7)
    5. July (12)
    6. June (18)
    7. May (22)
    8. April (11)
    9. March (25)
    10. February (17)
    11. January (22)
  2. 2018 (219)
    1. December (2)
    2. November (32)
    3. October (27)
    4. September (26)
    5. August (4)
    6. July (9)
    7. June (13)
    8. May (17)
    9. April (13)
    10. March (28)
    11. February (27)
    12. January (21)
  3. 2017 (281)
  4. 2016 (335)
  5. 2015 (209)
  6. 2014 (235)
  7. 2013 (251)
  8. 2012 (135)