Midwest Computability Seminar


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.

: Thursday, April 18th, 2019.
PLACE: Ryerson Hall 352 (the Barn), The University of Chicago.
1100 East 58th Street, Chicago, IL 60637.




Wesley Calvert

Title: Probability, Density, and Structure

Abstract: This talk will give account of some converging trends at the intersection of logic and probability. Randomized computation, dense/generic/coarse computability, theories of random graphs and structures, and theoretical machine learning have subtle connections, and their points of contact pose interesting problems for mathematical logic. In addition to an exposition on several older results and their interactions, this talk will include some recent results on categoricity in an environment of generic and coarse computability.

Steffen Lempp

Title: Toward deciding the ∀∃-theory of the enumeration degrees

Abstract: I will outline an approach, in joint work with Slaman and M. Soskova, toward deciding the ∀∃-theory of the enumeration degrees. The procedure is necessarily more difficult than for the Turing degrees since the enumeration degrees are downward dense; however, by a result of Calhoun and Slaman, even the Π02-enumeration degrees are not dense. Kent and Lewis have extended this to show that there is a strong minimal cover in the Π02-enumeration degrees, and our work builds on extending that result.

Russell Miller

Title: Hilbert's Tenth Problem as an enumeration operator

Abstract: For a ring R, Hilbert's Tenth Problem is the set HTP(R) of polynomials fR[X0,X1,...] for which f = 0 has a solution in R. It has been known since the work of Davis, Putnam, Robinson, and Matiyasevich in 1970 that HTP(ℤ) is as hard as the Halting Problem, and indeed that every computably enumerable set is diophantine in ℤ, i.e., definable in ℤ by an existential formula, and thus decidable from HTP(ℤ). In contrast, the decidability of HTP(ℚ) is an open question.

It is natural to view HTP as a pseudojump operator, mapping each set W of prime numbers to the set HTP(ℤ[W-1]). (Every subring of ℚ is of this form, for some W.) One might hope to relate it to the jump operator, which maps W to its jump W'. In fact, though, HTP is an enumeration operator. We will discuss ways in which this distinguishes it from the jump operator. There do exist sets W (including the empty set) for which W' is diophantine in HTP(ℤ[W-1]), and indeed they occur in every Turing degree; on the other hand, under Lebesgue measure, they are quite rare. The weaker statement that HTP(ℤ[W-1]) at least computes W' is known to be false in certain cases, but remains open for most sets W. We will show that no single oracle Turing machine can accomplish this reduction uniformly on a set of rings of full Lebesgue measure.

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.