Overview
Date: Saturday, April 24, 2021
Time: Starting at 2pm (EST)
Place: Springfield College (online)
Schedule
(All times in EST time zone.)
| 1:45pm | General social time if anyone wants to log in early | |
| 2pm | Patrick Lutz (University of California, Berkeley) | Martin’s conjecture and ultrafilters on the Turing degrees |
| 2:50pm | Break | |
| 3:05pm | Bjørn Kjos-Hanssen (University of Hawaii at Manoa) | A family of metrics connecting Jaccard distance to normalized information distance |
| 3:30pm | Break | |
| 3:55pm | Sarah Reitzes (University of Chicago) | Reduction games over RCA0 |
Abstracts
Patrick Lutz (University of California, Berkeley)
Martin’s conjecture and ultrafilters on the Turing degrees
Martin’s conjecture is an attempt to make precise the idea that the only natural functions on the Turing degrees are the constant functions, the identity, and transfinite iterates of the Turing jump. The conjecture is typically divided into two parts. Very roughly, the first part states that every natural function on the Turing degrees is either eventually constant or eventually increasing and the second part states that the natural functions which are increasing form a well-order under eventual domination, where the successor operation in this well-order is the Turing jump.
In joint work with Benny Siskind, we have shown that part 1 of Martin’s conjecture is equivalent to a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees. We will review the Rudin-Keisler order, explain this equivalence and discuss some further questions it raises. We will illustrate our discussion with several examples, including an ultrafilter on the Turing degrees arising from Lebesgue measure.
Bjørn Kjos-Hanssen (University of Hawaii at Manoa)
A family of metrics connecting Jaccard distance to normalized information distance
Distance metrics are used in a wide variety of scientific contexts. In a 2001 paper in the journal Bioinformatics, M. Li, Badger, Chen, Kwong, and Kearney introduced an information-based sequence distance. It is analogous to the famous Jaccard distance on finite sets. Soon thereafter, M. Li, Chen, X. Li, Ma and Vitányi (2004) rejected that distance in favor of what they call the normalized information distance (NID). Raff and Nicholas (2017) proposed a return to the Bioinformatics distance, based on further application-informed criteria.
We attempt to shed some light on this “dispute” by showing that the Jaccard distance and the NID analogue form the extreme points of the set of metrics within a family of semimetrics studied by Jiménez, Becerra, and Gelbukh (2013).
The NID is based on Kolmogorov complexity, and Terwijn, Torenvliet and Vitányi (2011) showed that it is neither upper semicomputable nor lower semicomputable. Our result gives a 2-dimensional family including the NID as an extreme point. It would be interesting to know if any of these functions are semicomputable.
Sarah Reitzes (University of Chicago)
Reduction games over RCA0
In this talk, I will discuss joint work with Damir D. Dzhafarov and Denis R. Hirschfeldt. Our work centers on the characterization of problems P and Q such that P $\leq_{\omega}$ Q, as well as problems P and Q such that $\textup{RCA}_0 \vdash$ Q $\to$ P, in terms of winning strategies in certain games. These characterizations were originally introduced by Hirschfeldt and Jockusch. I will discuss extensions and generalizations of these characterizations, including a certain notion of compactness that allows us, for strategies satisfying particular conditions, to bound the number of moves it takes to win. This bound is independent of the instance of the problem P being considered. This allows us to develop the idea of Weihrauch and generalized Weihrauch reduction over some base theory. Here, we will focus on the base theory $\textup{RCA}_0$. In this talk, I will explore these notions of reduction among various principles, focusing particularly on bounding and induction principles.