Midwest
Computability Seminar
XXIII
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: Thursday, April 18th, 2019.
PLACE: Ryerson Hall 352 (the
Barn), The University of
Chicago.
1100 East 58th Street, Chicago, IL 60637.
Speakers:
- Wesley Calvert - Southern Illinois University
- Steffen Lempp - University of Wisconsin
- Russell Miller - Queens College - CUNY
Schedule:
- 12:00 - 1:00 Lunch
- 1:00 - 1:50 Wesley Calvert
- 2:00 - 2:50 Russell Miller
- 3:00 - 4:00 Coffee Break
- 4:00 - 4:50 Steffen Lempp
- 5:30 Dinner at Nella, 1125 E. 55th St.
Abstracts:
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 f ∈
R[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.