Incomputability and Randomness

Andrew Lewis-Pye

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.