1st Semester 2009/10: Algorithmic Randomness and Computability Theory

Instructors

George Barmpalias.
If you are interested in this project, please contact the instructor by e-mail.

ECTS

6

Description

This project will be a study on the interface between algorithmic randomness and computability theory. When is an infinite binary sequence algorithmically random? How much information can be coded into such a sequence? Information usually introduces structure, therefore makes objects non-random. The extend to which this statement holds depends on the randomness degrees considered (formalizations of randomness) and the measures of information used.

One of the most important largely open questions in the currently very active area between computability and algorithmic randomness is this:

How much information can a random sequence have without losing its randomness features?

In this project we will study aspects of this rather general questions, leading to interesting open problems in this area. One of the main purposes of this project is to introduce this very active area of research, the motivation and the techniques associated with it, and try to approach a number of open problems in this area.

In the first part the students will master a number of central techniques through existing results in the literature. Then we will try to use them to approach some open problems. In this respect, the second part of the project will have an open end to original research.

Prerequisites

The project is particularly suitable for those who are familiar with basic computability (recursion) theory or descriptive set theory. Basic intuition and working knowledge of the Cantor space, topology and Lebesgue measure in it will be useful.

Assessment

Each student will present a couple of the main results in the area and write a short essay at the end of the course, which may or may not contain original results. Participation in the discussions will form part of the assessment.

References

The main references will be Nies' book Computability and Randomness (Oxford Press) and the forthcoming book (2010) of Downey and Hirschfedt, Algorithmic randomness and complexity (Springer). These will be provided (for personal use) to the students who take this project.