Date | Time | Speaker | Title | Cookies, dinner, etc. |

Tuesday, December 8 | 4:00 p.m. | Tamvana Makuluni, UW | TBA | cookies/juice at 3:30 |

Thursday, January 28(Midwest Computability Seminar, University of Chicago)
| 1:00 p.m. | TBA | TBA | depart at 8:30 a.m. from Van Vleck loading dock/ lunch at noon in Ryerson/ dinner at 6 |

2:30 p.m. | TBA | TBA | ||

4:00 p.m. | TBA | TBA |

**Prerequisites:** Math 773

**Time and Place:** MWF 11:00-11:50

**Textbook:** none

**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.

Prepared by Steffen Lempp (@math.wisc.edu">lemppmath.wisc.edu)