Computability Learning SeminarExport this event to calendar

Wednesday, October 28, 2015 — 3:00 PM EDT

Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo

“Martin-Lof Randomness and Solovay Tests”

We have seen that the Martin-Lof random real numbers are a reasonably natural notion: they are definable both in terms of Martin-Lof tests and in terms of complexity.

In this lecture, we will offer some evidence that Martin-Lof randomness is not just a natural notion, but also a robust one. We will see that to be Martin-Lof random, it suffices to have high complexity on an infinite computable set of initial segment lengths, and that Martin-Lof randomness is preserved by finite errors, computable sampling, and indeed even by computable permutation. We will note in passing that it is however not a notion that respects the structure of the Turing degrees.

We will also offer a third characterization of Martin-Lof randomness by using Solovay tests. This will allow us to give a stronger bound on the length of runs of zeros in a Martin-Lof random real.

MC 5403

S M T W T F S
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
31
1
  1. 2020 (16)
    1. January (16)
  2. 2019 (199)
    1. December (7)
    2. November (26)
    3. October (19)
    4. September (13)
    5. August (7)
    6. July (12)
    7. June (18)
    8. May (22)
    9. April (11)
    10. March (25)
    11. February (17)
    12. January (22)
  3. 2018 (219)
  4. 2017 (281)
  5. 2016 (335)
  6. 2015 (209)
  7. 2014 (235)
  8. 2013 (251)
  9. 2012 (135)