Midwest Computability Seminar

XV


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 Chicago.
1100 East 58th Street, Chicago, IL 60637.


Speakers:

Schedule:


Abstracts:

Eric Astor

Title: Asymptotic density, immunity, and randomness

Abstract: We investigate a computably-invariant restriction of asymptotic density. 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.


Quinn Culver

Title: The interplay between varieties of algorithmically random objects

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.


Timothy McNicholl

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.


Jack Lutz

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

This is joint work with Adam Case.


Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.