Midwest
Computability Seminar
XIV
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: Tuesday, April 29, 2014.
PLACE: Ryerson Hall 352 (the
Barn), The University of
Chicago.
1100 East 58th Street, Chicago, IL 60637.
Speakers, with links to slides:
Schedule:
- 12:00 - 1:00: Lunch
- 1:00 - 1:50: Rod Downey
- 2:00 - 2:30: Gregory Igusa
- 2:40 - 3:10: Coffee Break
- 3:10 - 4:00: Noam Greenberg
- 4:10 - 4:40: Kyle Riggs
- 4:50 - 5:20: Alexander Melnikov
- 6:00: Dinner at Lao
Yunnan
Abstracts:
Rod Downey
Title: Integer Valued Randomness
Abstract: (with George Barmpalias and Michael McInerney) In 2012,
Bienvenu, Stephan and Teutsch began the study of an interesting
notion of algorithmic randomness called integer valued randomness.
This notion asks that we use martingales where the bets need to have
discrete
values. We will review the known results in this area, and
look at recent material classifying the relationship of the
randomness notion with the computably enumerable degrees, and
notions of genericity.
The notions of genericity intertwine themselves with the
hierarchy of Δ^{0}_{2} degrees
of Downey and Greenberg.
Noam Greenberg
Title: Ordinals in Computability
Abstract: I will survey a number of projects all involving ordinal
numbers, ranging
from the study of the c.e. degrees to higher randomness and examining
effective properties of uncountable structures.
Gregory Igusa
Title: Generic Computability and Coarse Computability
Abstract: In 2012, Jocksuch and Schupp introduced generic
computability and coarse computability to study reals that are close
to being computable, not in the sense that they have very little
information in them, but rather in the sense that it is possible to
correctly compute the majority of their bits (in the sense of
asymptotic density.) A generic computation is one that usually halts,
and that is correct wherever it does halt, whereas a coarse
computation is one that always halts, usually correctly.
Neither of these two notions implies the other, but there is evidence that
suggests that in some sense, it is easier to be coarsely computable than it
is to be generically computable. We discuss the origins of these
asymmetries, and also some mention some surprising symmetries. We also look
at the coarsely computable reals from the point of view of the degree
structure for generic computation, allowing us to judge how "close" a
coarsely computable real is to being generically computable in a framework
that is natural for generic computations.
This work is partly joint work with Damir Dzhafarov
Alexander Melnikov
Title: Notions of Independence in Computable Commutative Algebra
Abstract: Typically a natural class of commutative algebraic structures
has
a notion of independence associated to this class. For example, we have
notions of independence for vector spaces, torsion-free abelian groups,
fields, differential fields, difference fields, etc. In my talk I will
give
a sufficient condition for a computable structure to have a computable
presentation with a computable basis. The condition implies all known
results of this nature. The condition also has several new applications,
most notably to various classes of fields with extra operations added to
the
field signature (e.g., difference closed fields).
We will also discuss a notion of independence in the context of abelian
p-groups. For this notion, the question of having a presentation with a
computable base has been open for over 20 years. I will state a result
which
perhaps explains why the question seems difficult.
Kyle Riggs
Title: The Decomposability Problem for Torsion-Free Abelian Groups is
Analytic-Complete
Abstract: We discuss the decomposability of torsion-free abelian groups. We
show that among computable groups of finite rank this property is
arithmetical. However, when we consider groups of infinite rank, it
becomes analytic-complete, so it cannot be characterized by a first-order
formula in the language of arithmetic.
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.
- Nov 15th 2012 Achilles Beros
- Rod Downey - Jesse Johnson - Sam Sanders - Steven VanDendriessche -
Matthew Wright.
- April 2nd 2013 Howard
Becker - Denis Hirschfeldt - Paul Schupp.
- October 1st 2013 Peter Cholak
- Mushfeq Khan - Victor Ocasio-González - Jonathan Stephenson
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.