Incomputability and Randomness
- Date: Wednesday 28 November 2018, 16:15 – 17:15
- Location: Mathematics Level 8, MALL 1, School of Mathematics
- Type: Logic, Seminars, Pure Mathematics
- Cost: Free
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.