Topic Archive: NERDS
The Autumn 2016 meeting of NERDS, the New England Recursion and Definability Seminar, will take place on Sunday, November 6 at Wellesley College, in Wellesley, MA. Details are available from the NERDS website, and talks are also posted here on nylogic.org.
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.
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.
Consider a convergence theorem of the following form.
(T): If the property P holds, then the sequence (xn) 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 axiomatizable in continuous logic, then the corresponding metastable bounds are both uniform and computable from P. This generalizes both of the previous results.
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., ∅-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.
The 2015 autumn meeting of the New England Recursion & Definability Seminar will be held on the campus of Assumption College, in Worcester Massachusetts, on Saturday, October 17, from 10:00 until 4:15. Titles and abstracts are now posted at the link for NERDS, under the Seminars tab. Directions and visitor information are available here.