SWLC Schedule

Refreshments will be served in the 9th floor lounge a half hour before talks. Please check the schedule below. All talks will be in 901 Van Vleck Hall unless stated otherwise.

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

Math 873 - Spring 2016 - Topics in Logic - Effective Randomness and K-triviality

Instructor: Joe Miller

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.

Math 975 - Reading Seminar in Logic

Our reading seminar is meeting on Wednesdays at 3:30 in B119 Van Vleck Hall.

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