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, 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
loading dock/
lunch at 11:30 at Joy Yee's
(1335 S. Halsted)/
dinner at 5:30
2:30 p.m. TBA TBA
4:00 p.m. TBA TBA
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

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.

Abstracts of talks

McCarthy's talk: Slopes of computable real-valued functions

Let f be a real-valued function, computable in the classical sense of Lacombe and Grzegorczyk. In 1983, Pour-El and Richards established that if f is twice continuously differentiable, the derivative of f is itself a computable function. In particular, the values f'(x) are uniformly computable in x.

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.


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