Incomputability and Randomness

We’ll consider the relationship between incomputability and randomness. Most of the talk will be concerned with giving an introduction to the area (assuming no more background knowledge than basic definitions from computer science such as Turing machines). Towards the end we’ll get to discuss some recent research with my coauthor Barmpalias, which is concerned with the efficient coding of information into random sequences, giving a sort of combinatorial analogue of Shannon’s Source Coding Theorem.