Midwest Computability Seminar

Midwest Computability Seminar

XXXVI


The Midwest Computability Seminar is a joint venture between the University of Chicago, the University of Notre Dame, the University of Wisconsin-Madison, and the University of Illinois Chicago. It meets once or twice per semester, and is attended by faculty and students from these universities and others in the area. The seminar started in the fall of 2008.



DATE: Thursday, April 9th, 2026

PLACE: Daley Library room 1-470, University of Illinois Chicago
801 S. Morgan, Chicago IL
PLEASE NOTE THE NEW LOCATION


REMOTE ATTENDANCE: https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09
Meeting ID: 997 5433 2165
Passcode: midwest


Speakers:

Schedule:


Abstracts:


Patrick Lutz

Title: A Borel graphable equivalence relation with no Borel graphing of diameter 2

Abstract: An equivalence relation E on a Polish space X is Borel graphable if it is the connectivity relation of some Borel graph on X. This notion was introduced by Arant in his thesis and further studied in a paper by Arant, Kechris and myself. In the latter paper, it was observed that in many cases when an equivalence relation E is proved to be Borel graphable, the Borel graph used in the proof has diameter 2 (more precisely, the connected components of the graph each have diameter at most 2). This naturally raises the question of whether every Borel graphable equivalence relation has a Borel graphing with diameter 2. In this talk, we will show that this question has a negative answer. The proof relies on the computability-theoretic notion of genericity and a surprising lemma about genericity plays a key role in the proof.


Joseph Miller

Title: Nontotal continuous degrees: The robustness of pathology

Abstract: I will discuss a robust subclass of the nontotal continuous degrees. The continuous degrees measure the computability-theoretic content of elements of computable metric spaces, such as continuous real-valued functions on [0,1]. In 2004, I introduced the continuous degrees and proved that they properly extend the Turing degrees. To do this, I constructed a sequence α∈[0,1]ω such that if φeα↓∈ [0,1], then α(e) = φeα. In other words, α lists the α-computable reals from [0,1] in order. I said that such a sequence is diagonally not computably diagonalizable (DNCD). We still do not know if every nontotal (i.e., non-Turing) continuous degree contains a DNCD sequence. Some time later, I found out that Levin's neutral measures, introduced in 1976, already give examples of nontotal continuous degrees. Neutral measures are also pathological: they are measures on Cantor space for which every infinite binary sequence is random, even though tests have access to the measure itself. In this talk, I will discuss ongoing work with Dhruv Kulshreshtha, in which we show that the degrees of DNCD sequences coincide with those of (weakly) neutral measures. They are exactly the continuous degrees a such that every Turing degree above a is PA relative to a. They form a robust class, whether or not it is a proper subclass of the nontotal continuous degrees.


Antonio Nakid Cordero

Title: Ziegler Reducibility and Subshift Simulation

Abstract: The study of multidimensional subshifts---colorings of ℤd that avoid a set of forbidden finite patterns---has seen recent successes through the application of tools from computability theory. In this work, we give a purely computability-theoretic characterization of when a subshift, with access to a finite amount of extra information, can "completely determine" another subshift. Our characterization is based on a reducibility used by Ziegler to study the finitely generated subgroups of existentially closed groups.

This is joint work with Isabella Scott.


Hongyu Zhu

Title: Degree spectra of structures of low Scott rank

Abstract:  The Scott rank of a countable structure M indicates how complex an infinitary formula needs to be in order to characterize M up to isomorphism. Another measure of complexity for M is the degree spectrum, which captures all Turing degrees computing a copy of M. In an attempt to connect the two notions, we show that there are certain degree spectra which cannot arise from structures with Scott rank below a given ordinal. This is joint work with Uri Andrews, David Gonzalez, and Joseph S. Miller.


MORE ABSTRACTS TO COME


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.