The Midwest Computability
Seminar is a joint venture between the University of Chicago, the University
of Notre Dame, and the University of Wisconsin-Madison. It
meets once or twice per semester at the
University of Chicago, and is attended by faculty and students from these
universities and others
in the area. The seminar started in the
fall of 2008.
DATE: Tuesday, September 30, 2014.
PLACE: Ryerson Hall 352 (the
Barn), The University of
1100 East 58th Street, Chicago, IL 60637.
Eric Astor - Chicago
- Quinn Culver - Notre Dame
- Jack Lutz - Iowa State University
- Timothy McNicholl - Iowa State University
- 12:00 - 1:00: Lunch
- 1:00 - 1:25: Eric Astor
- 1:35 - 2:00: Quinn Culver
- 2:00 - 2:30: Coffee break
- 2:30 - 3:20: Jack Lutz
- 3:30 - 4:10: Coffee break
- 4:10 - 5:00: Timothy McNicholl
- 6:00: Dinner - La Lagartija, 132 S. Ashland Ave.
Abstracts: Eric Astor
Title: Asymptotic density, immunity, and randomness
Abstract: We investigate a computably-invariant restriction of asymptotic
This new pseudo-measure on the natural numbers has strong connections to
randomness and classical computability theory; we use it to define a new
immunity property, recognize a new form of stochasticity, and find an
unexpected connection to functions avoiding weak computable approximation.
We also apply similar ideas to create computably-invariant restrictions of
the generic-case computability defined by Jockusch and Schupp, and prove a
generalization of Rice's Theorem as a lower bound on their strength.
Title: The interplay between varieties of algorithmically random
Abstract: We study algorithmically random closed subsets of cantor space,
algorithmically random continuous functions from cantor space to cantor
space, and algorithmically random Borel probability measures on cantor
space; especially the interplay between the three. Our main tools are
preservation of randomness and its converse, no randomness ex nihilo, which
say together that given an a.e.-defined computable map between an
effectively compact probability space and an effective polish space, a real
is (Martin-Löf) random for the pushforward measure if and only if its
preimage is random for the domain's measure. These tools allow us to prove
new facts, many of which were previously open questions, and reprove some
known results more simply. This work is joint with Chris Porter.
Title: Interactions between computability and complex analysis
Abstract: We will discuss computability issues in the study of analytic
functions; in particular recent work on computability properties of
functions in the Hardy spaces.
Title: Mutual dimension
Abstract: The search for a satisfactory notion of the mutual information between two
infinite sequences is a major open problem in algorithmic information
theory. This talk discusses our recent solution of a closely related
problem, the correct formulation of the mutual dimension (density of shared
information) between two points in Euclidean space. We define mutual
dimension and show that it satisfies the desiderata for such a quantity,
most crucially the data processing inequality, which says that the action of
a computable Lipschitz function cannot increase a point's mutual dimension
with any other point. Extensions and applications will be discussed as time
This is joint work with Adam Case.
- Sept 23th 2008. Antonio
Montalbán - Logan Axon - Joe Miller
- Nov 11th 2008. Chris
Conidis - Keng Meng (Selwyn) Ng - Peter Gerdes
- Feb 3rd 2009. David
Diamondstone - Bart Kastermans - Richard A. Shore
- April 21th 2009. Dan Turetsky
- Julia Knight - Ted Slaman
- Sept 29th 2009. Carl Jockusch
- Rachel Epstein - Rebecca Weber
- Jan 26th 2010. Sara Quinn -
John Wallbaum - Steffen Lempp - Reed Solomon
- May 11th 2010. Adam Day -
Liang Yu - Rod Downey - Boris Zilber
- Sept 28th 2010. Maurice
Chiodo - Peter Gerdes - Damir Dzhafarov - Andy Lewis
- Feb 15th 2011. Uri Andrews -
Paola D'Aquino - David Diamondstone - Christopher Porter -
- Nov 1st 2011. Mingzhong Cai -
Chris Conidis - Stephen Flood -
Jeff Hirst - Asher Kach.
- Nov 15th 2012 Achilles Beros
- Rod Downey - Jesse Johnson - Sam Sanders - Steven VanDendriessche -
- April 2nd 2013 Howard
Becker - Denis Hirschfeldt - Paul Schupp.
- October 1st 2013 Peter Cholak
- Mushfeq Khan - Victor Ocasio-González - Jonathan Stephenson
- April 29th, 2014 Rod Downey -
Noam Greenberg - Gregory Igusa - Alexander Melnikov - Kyle Riggs
If you haven't
been receiving the announcements and would like to be included
in the list, send an email to firstname.lastname@example.org.