Midwest Computability Seminar


The Midwest Computability Seminar meets twice in the fall and twice in the spring at University of Chicago.  Researchers in computability theory and their students and postdocs from University of Chicago, University of Notre Dame, and University of Wisconsin-Madison plus some others throughout the area regularly attend. Normally we have two half hour talks and two 1-hour talks and a few hours to talk and collaborate with each other.  The seminar started in the fall of 2008.

: Tuesday, May 11th, 2010.
PLACE: Ryerson, University of Chicago.
1100 East 58th Street, Chicago, IL 60637.




Adam Day -  Victoria University of Wellington, New Zealand.
Title: Indifferent sets for genericity
Abstract: Given a class C of {0,1} sequences and  a set of natural numbers I, we say that I is indifferent for some A in C if any other sequence  that differs from A only on the elements of I is also in C. The idea of an indifferent set was introduced by Figueira, Miller and Nies, who investigated indifferent sets for different notions of randomness. Similar ideas were used by Barmpalias, Lewis and Ng to show that every p.a. degree is the join of two randoms. We will look at indifferent sets when C is the class of  generic, or  weak generic sequences. We will show that for all generic sequences G, there is some infinite set I such that I is indifferent for G. We will consider the computational complexity of indifferent sets as well as the question as to whether a generic sequence can compute an infinite set to which it is indifferent.
 (joint work with Andrew Fitzgerald)

Liang Yu - Nanjing University, Nanjing, China.
Title: On strong Pi^1_1-ML-randomness
Abstract: we show that strong \Pi^1_1-randomness is strictly stronger than \Pi^1_1-ML-randomness.

Rod Downey - Victoria University of Wellington, New Zealand.
Title: Euclidean Function of Computable Euclidean Domains.
Abstract: One of the first algorithms discussed in almost any elementary  algebra course is Euclid’s algorithm for computing the greatest common divisor  of two integers. In a first course in abstract algebra, this idea is explained by  describing both Z and Q[X] as Euclidean domains. We recall the definition of  a Euclidean domain.
  Definition 0.1. A commutative ring  R is a Euclidean domain if it is an  integral domain (i.e., there are no zero divisors) and there is a function φ :  R  \{0} → ω satisfying
( ∀a, d ∈ R)(∃q ∈ R) [d = 0 or a + qd = 0 or φ(a + qd) < φ(d)] .
  If there is such a function φ : R \{0} → ON (where ON is the class of ordinals),
then R is a transfinite Euclidean domain.
  In the former case, we say the function φ is a (finitely-valued) Euclidean  function for  R; in the latter case, we say the function φ is a transfinitely-valued  Euclidean function for  R.
  It is still a forty year old open question (implicitly a sixty year old open  question) in algebra whether there exists a transfinite Euclidean domain having  no finitely-valued Euclidean function.
  Less well known is that we can define a Euclidian domain via a hierarchy  of sets with the property that it exhausts the set R \{0} of nonzero elements  if and only if  R is a (transfinite) Euclidean domain. At the bottom level R0  of this hierarchy, we have the units. At the next level R1 , we have all those  elements which either exactly divide all elements or give remainder a unit upon division. More generally, at level Rα , we have all those elements which either  exactly divide all elements or give remainder in R<α upon division.
  This defines a minimal Euclidian function. In this talk I will look at the  effective content and the reverse mathematics of Euclidian domains and in  particular the existence of minimal Euclidian functions. Lots of open questions  remain. The talk will be at a reasonably elementary level, notable more for  wonderful open questions rather than the depth of the theorems. 
   (Joint work with Asher Kach.)

Boris Zilber
Title: Some issues between Model Theory and Physics.
Abstract: I am going to talk about Zariski structures arising in the context of noncommutative geometry and physics and report on an ongoing project, initiated by physicists, that relates topos theory to physics and model theory.

Previous Seminars:

   If you haven't been receiving the announcements, and you would like to be included in the list, send me an email to antonio at uchicago.edu.