Incomputability and Randomness

Andrew Lewis-Pye, London School of Economics. Part of the Logic Seminar Series.

After a refresher on the Turing degrees, I'll give an introduction to algorithmic randomness.  Then we'll go on to consider the relationship between incomputability and randomness.  How incomputable can random sequences be?  Where in the Turing universe do most random objects lie?  We'll finish by looking at some recent work of mine with Barmpalias, which concerns the extent to which information (in the form of infinite binary sequences) can be compressed, and in which we obtain a combinatorial analogue of Shannon's Source Coding Theorem.