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
- 12:00 - 1:00: Lunch: Math Department Tea Room, 2nd
floor of Eckhart Hall (Eckhart Hall and Ryerson Hall are connected)
- 1:15 - 1:40: Matthew Wright
- 1:45 - 2:10: Steven VanDendriessche
- 2:15 - 3:05: Rod Downey
- 3:05 - 3:45:
Coffee Break
- 3:45- 4:10: Jesse Johnson
- 4:15 - 4:40: Achilles Beros
- 4:45 - 5:10: Sam Sanders
- 5:45: Dinner: The
Snail, 1649 E. 55th Street
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:
- Sept 23th 2008. Antonio
Montalbán - Logan Axon - Joe Miller
- Nov 11th 2008. Chris
Conidis - Keng Meng (Selwyn) Ng - Peter Gerdes
- Feb 3rd 2009. David
Diamondstone - Bart Kastermans - Richard A. Shore
- April 21th 2009. Dan Turetsky
- Julia Knight - Ted Slaman
- Sept 29th 2009. Carl Jockusch
- Rachel Epstein - Rebecca Weber
- Jan 26th 2010. Sara Quinn -
John Wallbaum - Steffen Lempp - Reed Solomon
- May 11th 2010. Adam Day -
Liang Yu - Rod Downey - Boris Zilber
- Sept 28th 2010. Maurice
Chiodo - Peter Gerdes - Damir Dzhafarov - Andy Lewis
- Feb 15th 2011. Uri Andrews -
Paola D'Aquino - David Diamondstone - Christopher Porter -
Rebecca Steiner.
- Nov 1st 2011. Mingzhong Cai -
Chris Conidis - Stephen Flood -
Jeff Hirst - Asher Kach.
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.