|Tuesday, February 16||4:00 p.m.||Ethan McCarthy, UW||Slopes of computable real-valued functions (see abstract)||cookies/beverages at 3:30|
|Tuesday, February 23||4:00 p.m.||Paul Tveite, UW||TBA||cookies/beverages at 3:30|
|Tuesday, March 1||4:00 p.m.||Wim Ruitenburg, Marquette University, Milwaukee, Wisconsin||TBA||cookies/beverages at 3:30|
|Tuesday, March 8||4:00 p.m.||Iván Ongay Valverde, UW||TBA||cookies/beverages at 3:30|
|Tuesday, March 15||4:00 p.m.||Tim McNicholl, Iowa State University, Ames||TBA||cookies/beverages at 3:30/|
dinner at 6 TBA
|Tuesday, March 29||4:00 p.m.||Noam Greenberg, Victoria University of Wellington, New Zealand||TBA||cookies/beverages at 3:30/|
dinner at 6 TBA
|Tuesday, April 5|
(Midwest Model Theory Day,
University of Illinois at Chicago)
|1:00 p.m.||TBA||TBA||depart at 8:30 a.m.|
from Van Vleck
lunch at 11:30 at Joy Yee's
(1335 S. Halsted)/
dinner at 5:30
|Tuesday, April 12||4:00 p.m.||Paul Schupp, University of Illinois at Urbana-Champaign||TBA||cookies/beverages at 3:30/|
dinner at 6 TBA
|Tuesday, April 19||4:00 p.m.||Turbo Ho, UW||TBA (thesis defense)||cookies/beverages at 3:30|
|Tuesday, April 26||4:00 p.m.||Tamvana Makuluni, UW||TBA||cookies/beverages at 3:30|
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.
Viewed in this light, this result tells us that analytic tameness of a real valued function yields upper bounds on the computational complexity of the values of its derivatives. We attempt to fill out this picture in further detail by answering questions of the following form: given f with some degree of good analytic behavior, what computational complexity may be achieved in the values of its derivative?
We consider several ways to tune this question, by varying the analytic conditions imposed on f (we will consider both differentiability and smoothness conditions) along with what sort of complexity we expect of f'(x) and with what level of uniformity.