Computability Learning SeminarExport this event to calendar

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

Mohammad Mahmoud, Pure Mathematics, University of Waterloo

"Algorithmic Randomness: Introduction to Kolmogorov Complexity"

Last time we saw why the Kolmogorov complexity $K$ can be better than the plain complexity $C$ as it is subadditive and complexity doesn't dip. This time we are going to see more properties showing that $K$ matches our intuition. More precisely, (a) Incompressible (in the sense of $K$) strings have only short runs of zeros (i.e. blocks only consisting of zeros), and (b) Zeros and ones occur balancedly.

MC 5403

S M T W T F S
30
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
31
1
2
3
  1. 2023 (169)
    1. June (2)
    2. May (35)
    3. April (21)
    4. March (51)
    5. February (33)
    6. January (27)
  2. 2022 (179)
    1. December (8)
    2. November (31)
    3. October (24)
    4. September (17)
    5. August (9)
    6. July (15)
    7. June (14)
    8. May (13)
    9. April (14)
    10. March (15)
    11. February (12)
    12. January (7)
  3. 2021 (135)
  4. 2020 (103)
  5. 2019 (199)
  6. 2018 (212)
  7. 2017 (281)
  8. 2016 (335)
  9. 2015 (211)
  10. 2014 (235)
  11. 2013 (251)
  12. 2012 (135)