Project on Randomness and Computability


Year: 2010
ECTS: 6
Lecturer: George Barmpalias
Participants:
  • Antonio Florio
  • Tom Sterkenburg
  • Aggelos Tsolakis
  • Charlotte Vlek
Meetings:

WEEK 1: Monday 2-4 Office: C3.138 , Thursday 2-4 Office: C3.138
WEEK 2: Monday 1-3 at A1.08, Thursday 11-1 at A1.14
WEEK 3: Monday 1-3pm at A1.08, Thursday 10-12 at A1.04
WEEK 4: Monday 1-3pm at A1.08, Thursday 11-1 at A1.04

Schedule / Assesment: The project will run in the four weeks of January. In the first week the students will obtain (or refresh) the necessary background on computability theory and Kolmogorov complexity (e.g. a number of basic results from Chapters 1,2 from Nies' book, see below). In the second week I will present some central results in the area, like the construction of a non-computable K-trivial sequence and the Kucera-Gacs coding into random sequences. In the third week each student will prepare a presentation of a substantial result in the area, like the coincidence of halting probabilities with Omega-like numbers, the incompleteness of the K-trivial sequences etc. This presentation will be the first stage of assessment. In the fourth week each student will write a paper (under my guidance) preferably containing some original result (or a substantially original presentation of a known result). The quality of the paper is the second stage of assessment. Finally each student will present the paper, and the third and final stage of assessment will be based on the quality of this presentation.


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.

Bibliography:

Algorithmic randomness and complexity, by Denis Hirschfeldt and Rodney Downey (Springer-Verlag)

Computability and randomness, by Andre Nies (Oxford Logic guides)

Introduction in Kolmogorov complexity and applications, by M. Li and P. Vitanyi (Springer)

Oscillation in the initial segment complexity of random reals, by Miller and Yu, to appear in Adv. Math.

Randomness, Lowness and Degrees, by Barmpalias, Lewis and Soskova, J. Symb. Logic 73 (2008).

A characterization of c.e. random reals, by Chris Calude, Theoretical Computer Science 271 (2002)