Overview
Date: Saturday, October 17, 2015
Time: 10:00 am–4:10 pm
Place: Assumption College, Carriage House (Visitor information)
Schedule
| 10:00–10:15 | Coffee and muffins | |
| 10:15–11:15 | Tyler Markkaenen (Springfield College) | A-Computable Graphs |
| 11:25-12:25 | Jason Rute (Pennsylvania State University) | Computing uniform (metastable) rates of convergence from the statement of the theorem alone |
| 12:30-1:45 | Lunch (Taylor Dining Hall. Funded by the Assumption College Provost’s Office.) | |
| 1:45–2:00 | Coffee | |
| 2:00–3:00 | Valentina Harizanov (George Washington University) | Computably enumerable sets and vector spaces with thin complements |
| 3:10–4:10 | Quinn Culver (Fordham University) | The interplay of classes of algorithmically random objects |
Abstracts
Tyler Markkaenen
A locally finite computable graph G is called A-computable if A can compute the neighbors of the vertices of G. William Gasarch and Andrew Lee introduced this notion to study graphs that are “between” computable and highly computable (i.e., \emptyset-computable). For any noncomputable c.e. set A, they proved that the A-computable graphs behave just like computable graphs when it comes to colorings. In this talk, we will see that their result also works for Euler paths and domatic partitions. Although it does not extend to arbitrary sets A (that are not necessarily c.e.), we will classify the sets for which it does.
Jason Rute
Consider a convergence theorem of the following form.
(T): If the property P holds, then the sequence (x_n) converges.
For example, the monotone convergence principle states that any monotone, bounded sequence of reals converges.
This talk concerns the notion of metastable rates of convergence. The advantage of this notion is that metastable rates are often uniform and computable. Kohlenbach, using proof theory, showed that if the property P is of a certain form and the theorem (T) is provable in a certain formal type theory, then the rate of metastable convergence is both uniform and computable. Avigad and Iovino, using model theory, showed that if the theorem (T) is true and the property P is preserved by ultraproducts, then the rate of metastable convergence is uniform (no mention of computability). In this result, using computable analysis and computable continuous model theory, we show that if (T) is true and P is axiomitizable in continuous logic, then the corresponding metastable bounds are both uniform and computable from P. This generalizes both of the previous results.
Valentina Harizanov
Simple, hypersimple, hyperhypersimple, and maximal sets play an important role in computability theory. Maximal sets are co-atoms in the lattice of computably enumerable sets modulo finite sets. Soare established that they are automorphic in this lattice. Similarly, maximal vector spaces play an important role in the study of the lattice of computably enumerable vector spaces modulo finite dimension. We will investigate principal filters determined by maximal spaces and how algebraic structure interacts with computability-theoretic properties. We will discuss the problem of finding orbits of maximal spaces under lattice automorphisms, the development of various notions of maximality for vector spaces, and recent progress that is joint work with R. Dimitrov.
Quinn Culver
We study algorithmically random closed subsets (RCS’s) of Cantor space, algorithmically random continuous functions (RCF’s) from Cantor space to Cantor space, and algorithmically random Borel probability measures on Cantor space; especially the interplay between the three. Our main tools are preservation of randomness (PoR) and its converse no randomness ex nihilo (NREN), which say together that given an a.e.-defined computable map between an effective probability space and an effective polish space, a real is (Martin-Löf) random for the pushforward measure if and only if its preimage is random for the domain’s measure. PoR and NREN allow us to prove new facts that were previously open and reprove some known results more simply. Example 1: it was known that every RCS contains a random real and that every random real is contained in some RCS; we reprove this using PoR and NREN. Example 2: It was shown previously that the zero set (that is, the preimage of the sequence of all 0’s) of a RCF is a RCS. We reprove this using PoR and get the converse, which was previously left open, that ever RCS is the zero set of some RCF, via NREN. We also prove some miscellaneous results about the individual objects. Example 3: the Lebesgue measure of the range of a RCF is strictly between 0 and 1. This work is joint with Chris Porter.