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:


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 Δ02 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:

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.