Midwest Computability Seminar

XI


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, November 15, 2012.
PLACE: Ryerson Hall, The University of Chicago.
1100 East 58th Street, Chicago, IL 60637.


Speakers, with links to slides if available:

Schedule: All talks will be in the Barn, Ryerson 352

Abstracts:

Speaker: Achilles Beros
Title: Anomalous Vacillatory Learning
Abstract: In 1986, Osherson, Stob and Weinstein asked whether two variants of anomalous vacillatory learning, TxtFex$^*_*$ and TxtFext$^*_*$, are distinct. These two learning criteria place bounds neither on the number of hypotheses between which the learner is allowed to vacillate nor on the number of errors permitted, merely requiring that both are finite. The criteria differ in that the more restrictive one requires that all hypotheses output infinitely often must describe the same finite variant of the correct set, while the other permits the learner to vacillate between finitely many different finite variants of the correct set. We exhibit a family that distinguishes the two types of learning, thereby answering the question posed by Osherson, et al. We prove this in a strong way, learning the family with a machine that vacillates between only two hypotheses.

Speaker:Rod Downey
Title: The Finite Intersection Property and Computability Theory
Abstract: A family of sets ${\mathcal F}=\{A_i\mid i\in J\}$ has FIP iff for any finite $I\subset J$, $\cap_{i\in I}A_i\ne \emptyset.$ The FIP principle says that any collection of sets has a maximal subcollection with FIP. The reverse maths and effective content of this principle, classically equivalent to AC, was initiated by Dzhafarov and Mummert. They showed, for instance, that there is a computable family with no computable maximal FIP subfamily. We say that a degree ${\bf a}$ is FIP iff it has the ability to compute a solution to any computable instance of FIP. Dzhafarov and Mummert's result says that ${\bf 0}$ is \emph{not} FIP. Dzhafarov and Mummert showed that each nonzero c.e.\ degree is FIP, all FIP degrees are hyperimmune, and several classes of 1-generics degree were FIP.

We extend these investigations by giving new (shorter) proofs of some of Dzhafarov and Mummert's work. Then we show that all 1-generics are FIP, and that for the $\Delta_2^0$ degrees that the FIP degrees are precisely the ones that bound 1-generic degrees. We could hopw that this characterization extends to the general hyperimmune case, since hyperimmune degrees resemble delta 2 ones. However, we can also show that there is a minimal $\Delta_3^0$ FIP degree. This last result has some technical complexity as it is a full approximation argument constructing a hyperimmune $\Delta_3^0$ degree, which does not seem to have occurred in the literature hitherto.

We also investigate finite versions of the principles, such as the case of FIP, $\overline{D}_2$IP (every pair has nonempty intersection) where all the sets must be finite, and say, given by c.e.\ indices.

Speaker:Jesse Johnson
Title: Computable Categoricity in the Setting of $\omega_1$-Computability
Abstract: We describe a notion of computability for uncountable structures using tools from $\alpha$-recursion for $\alpha=\omega_1$.  We define computable categoricity in this setting and give a couple of examples using these definitions.  We then show that the ``covers of the multiplicative group of $\mathbb{C}$" are relatively computably categorical, but a model-theoretically similar class, the ``pseudo-exponential fields" are not even computably categorical.

Speaker:Sam Sanders
Title: Nonstandard Analysis: A New Way to Compute
Abstract: Constructive Analysis (aka BISH) was introduced by Errett Bishop as a redevelopment of Mathematics with a focus on computational content. As such, BISH is based on the BHK (Brouwer-Heyting-Kolmogorov) interpretation of logic, where the notions of `proof' and `algorithm' are central. Constructive Reverse Mathematics (CRM) is a spin-off from Harvey Friedman's `Reverse Mathematics' program where the base theory is based on BISH.

In this talk, we introduce an interpretation of BISH in classical Nonstandard Analysis. The role of `proof' in this interpretation is played by the Transfer Principle of Nonstandard Analysis. The role of `algorithm' is played by `$\Omega$-invariance'. Intuitively, an object is $\Omega$-invariant if it does not depend on the *choice* of infinitesimal used in its definition. Using this new interpretation, we obtain many of the well-known results form CRM. In particular, all non-constructive principles (like LPO, LLPO, MP, etc) are interpreted as Transfer Principles, which are not available in our nonstandard base theory. We also focus on how Recursive Mathematics is interpreted in Nonstandard Analysis by studying Markov's principle.

Speaker:Steven VanDendriessche
Title: Maxima for the $\leq_{tc}$ Ordering with Respect to $\sim^c_\alpha$
Abstract: The Turing computable embedding is an effective reduction of the isomorphism relation on a class of countable structures $K$ to that on $K'$. When such an embedding exists, we write $K\leq_{tc}K'$, indicating that the isomorphism problem for $K'$ is at least as difficult as that for $K$. The relation $\leq_{tc}$ is a preordering on classes of countable structures, and it is known that there is a maximum degree in this order. Motivated by the importance of computable infinitary sentences in this work, we define the equivalence relation $\sim^c_\alpha$ on structures, where $\mathcal{A}\sim^c_\alpha \mathcal{B}$ if and only if $\mathcal{A}$ and $\mathcal{B}$ satisfy the same computable infinitary $\Sigma^0_\alpha$ sentences. For any $\alpha<\omega_1^{ck}$, we give a subclass of the countable reduced abelian $p$-groups which is a maximum for the $\leq_{tc}$ ordering with respect to $\sim^c_\alpha$. Further, these embeddings are highly uniform, and we describe work toward constructing an operator witnessing that the abelian $p$-groups are a maximum for $\leq_{tc}$ with respect to $\sim^c_{\omega_1^{ck}}$. Finally, we show that if $ZFC$ has an $\omega$-model, then it is consistent that the abelian $p$-groups are a maximum with respect to $\sim^c_{\omega_1^{ck}}$.

Speaker:Matt Wright
Title: Degrees of Relations on Ordinals
Abstract: Downey, Khoussainov, Miller, and Yu showed that the degree spectrum of any computable unary relation on $(\omega,<)$ either contains only the computable degree, or contains $\zero'$. We will show, using Ramsey's theorem and results about well quasi orderings, that their result can be extended to arbitrary computable relations on $(\omega,<)$. We will further show, using results about back and forth relations, that their result can also be generalized to work in the case of computable unary relations on arbitrary computable ordinals; specifically, that the degree spectrum of such a relation always contains a maximum degree and that that degree is always an iterate of the jump.

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.