|Tuesday, December 8||4:00 p.m.||Tamvana Makuluni, UW||TBA||cookies/juice|
|Thursday, January 28|
(Midwest Computability Seminar,
University of Chicago)
|1:00 p.m.||TBA||TBA||depart at 8:30 a.m.|
from Van Vleck
lunch at noon in Ryerson/
dinner at 6
Prerequisites: Math 773
Time and Place: MWF 11:00-11:50
Course Description: Kolmogorov complexity was introduced in the mid-1960's as a measure of the "information content" of finite binary strings. The Kolmogorov complexity of a string is the length of the shortest program (in a sufficiently powerful, binary encoded programming language) that outputs the string. Incompressible strings are sometimes called "random". Also in the mid-1960's, Martin-Löf, a student of Kolmogorov, introduced what has become the most successful notion of effective randomness for infinite binary sequences. Although there were obvious connections between Martin-Löf randomness and Kolmogorov complexity, the picture became more clear with the introduction of a variant of Kolmogorov complexity in the mid-1970's, independently by Levin and Chaitin. This notion, prefix-free complexity, permits a natural characterization of the Martin-Löf random sequences as those with incompressible initial segments.
The focus of this course will be on a class of sequences that has been very actively studied in recent years: the K-trivial sequences. These are the sequences with minimal initial segment prefix-free complexity; in other words, they are no more complex than the sequence of all zeros. In 1975, Solovay constructed a non-computable K-trivial sequence, but the class remained obscure until the early 2000's when a series of seminal papers established its importance, in part by giving several nontrivial characterizations. Some examples of these and later characterizations: A is K-trivial iff every Martin-Löf random sequence is Martin-Löf random relative to A; iff there is a sequence Martin-Löf random relative to A that computes A; iff any Martin-Löf random sequence that joins A above 0' must itself compute 0'; iff the symmetric difference of A with a Martin-Löf random sequence yields a Martin-Löf random sequence. Along with many surprising and deep characterizations came a better understanding of K-triviality. For example, the K-trivial sequences form an ideal in the Turing degrees and every K-trivial sequence is computable from a c.e. K-trivial.
Although the study of K-triviality will drive the course, no previous knowledge of effective randomness will be assumed, so we will necessarily cover a great deal of background. A basic knowledge of computability theory will be assumed.