Project on Randomness and Computability II (June 2010)

Year: 2010

ECTS: 6

Lecturer: George Barmpalias

Meetings: Twice a week.

Participants: Martijn Baartse and Daan Staudt

Schedule / Assesment: The project will run in the four weeks of June. It is a continuation of the first Project on Randomness and computability that ran successfully in January 2010, see Project on Randomness and computability I. In this current project there will be an option of studying a topic on classical computability theory. 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. 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. By taking this project and working on it, students will: Improve their background on Computability theory Learn the topic of algorithmic randomness and its relation with computability theory Be exposed to contemporary research in the area.

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.

Personal account of the project, by Daan Staudt (from his project report): The goal of the Algorithmic Randomness and Computability project is for the students to investigate the relationship between the randomness properties of sets and their computational properties. Both students that participated in the project had previously been exposed to basic computability theory, but had little to no experience in the field of algorithmic randomness. The project started by reviewing the basic concepts from computability theory and algorithmic randomness that would be needed to study important results in the field and prove new ones. Several randomness notions were introduced, such as Martin-Löf randomness and (weak) 2-randomness. Both the plain Kolmogorov complexity and the prefix-free Kolmogorov complexity were passed in review and there relation was studied. Several lowness notions were also discussed, such as lowness for Martin-Löf randomness, for Kolmogorov randomness and for Chaitin's number. Apart from the concepts the participants were previously accustomed to from computability theory, DNC and PA sets were introduced as well as hyperimmune and hyperimmune-free sets and degrees. Once the participants had gotten used to the concept in play, they proceeded with a review of a selection of important results that relate computability to randomness in the context of sets and classes. The results discussed included for example that every set is computed by a 1-random, that hyperimmune sets are not 1-random and that every 2-random is CEA. This paper contains a presentation of the proofs of several new theorems on algorithmic randomness and computability....

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.

Basic 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)