GRADUATE COURSE: Measure, Computability and Randomness

OVERVIEW: Algorithmic Randomness is a multidisciplinary area which
involves Measure theory, probability,
Computability, complexity, and stochasticity. In this course I will
discuss selected topics on
randomness from an effective measure-theoretic point of view. We will
work on the Cantor space with the
usual topology and Lebesgue measure and look into what it means for a
sequence to be random, typical, one
which lacks special features, unpredictable, one which avoids all
effective statistical tests.
The notion of Turing machines or computable function will underly
almost everything we do, while classical results
from measure theory (though not very advanced) will play a role in
the arguments.
I will distribute some notes with most of the stuff that I'm going to
discuss so that you have a main reference.

BACKGROUND: A basic knowledge of topology and measure as well as an
intuitive understanding of computability will
help.

REFERENCES:   

My notes will probably be enough, but the following EBL library books
may be helpful.
The randomness references are probably most relevant (they also
contain the background material which we need), but
I also give references about computability and measure theory as
these are good books and one might be interested to
refer to them. Also the books under RANDOMNESS have not been fully
written or published but they can be downloaded
from the addresses given below.

COMPUTABILITY:

[1] P. Odifreddi: classical recursion theory
[2] S.B. Cooper:  Computability theory

MEASURE THEORY:
 
[1] Oxtoby: Measure theory (Graduate texts in mathematics)
[2] J. Doob: Measure theory (Graduate texts in mathematics) (this is
more probability-oriented)

RANDOMNESS:

[1] Downey and Hirschfeldt: Algorithmic Randomness
(http://www.mcs.vuw.ac.nz/~downey/randomness.pdf)
[2] Nies: Computability and Randomness
(http://www.cs.auckland.ac.nz/~nies/Niesbook.pdf)