Midwest Computability Seminar

Midwest Computability Seminar

XXXI


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


VIDEOS:   Cholak    Gonzalez    Royer (Part 1)  Royer (Part 2)    (Panopto)    Cholak    Gonzalez    Royer (Part 1)    Royer (Part 2)    (YouTube)

SLIDES:    Gonzalez    Royer



DATE: Tuesday, November 7th, 2023

PLACE: John Crerar Library Building 390, The University of Chicago.
5730 South Ellis Avenue, Chicago, IL 60637 (see maps.uchicago.edu).

PLEASE NOTE THIS IS NOT OUR USUAL BUILDING.

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


Speakers:

Schedule:

Abstracts:


Peter Cholak

Title: Some Computability Theoretic Aspects of Dobrinen’s Result that the Universal Triangle Free Graph Has Finite Big Ramsey Degree

Abstract: We will discuss recent work of Cholak, Dobrinen, and McCoy. Mostly we will focus on colorings within the universal triangle free graph of nodes, edges, and non edges. The result that the universal triangle free graph has finite big Ramsey degree implies for colorings of nodes, edges, or non edges there is a copy of the universal triangle free graph with a minimal number of colors. The minimum depends on the objects we are coloring, not the coloring itself. We will discuss this number for our 3 cases. A copy of the universal triangle free graph with a minimal number of colors is called a minimal heterogeneous copy. We will also discuss what is known about the computability theoretic complexity of these minimal heterogeneous copies.


David Gonzalez

Title: The omega-Vaught's Conjecture

Abstract: Robert Vaught conjectured that the number of countable models of any given list of axioms must be either countable or continuum, but never in between. Despite all the work that has gone into this conjecture over the past sixty years, it remains open. It is one of the most well-known, long-standing open questions in mathematical logic. We introduce the omega-Vaught's conjecture, a strengthening of Vaught's conjecture for infinitary logic. We have shown this conjecture holds for linear orderings, a strengthening of Vaught's conjecture for linear orderings originally proved by Steel. The approach notably differs from Steel's proof (and any other previously known proof of Vaught's conjecture for linear orderings) in that it makes no appeal to lemmas from higher computability theory or descriptive set theory. This talk is based on joint work with Antonio Montalbán.


Tiago Royer

Title: Asymptotic Notions of Computability

Abstract: In the classical setting, we consider that a Turing machine solves a problem if, for all inputs, the machine halts with the correct output for this problem. We can relax this notion by requiring the machine to halt and be correct only on asymptotically all inputs. If we still require the machine to always halt, we have coarse computability; if we allow the machine to not halt sometimes but require it to always be correct when it does, we have generic computability. I will talk about these notions and their degree structures, and I will present a proof that there are minimal degrees for coarse reducibility.


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.