Midwest Computability Seminar.


DATE: Tuesday, September 23, 2008  
PLACE: Ryerson Annex 277. University of Chicago.
1100 East 58th Street, Chicago, IL 60637.


Schedule:

Lunch: 12:00 at the Medici. 1327 E. 57th St, Hyde Park.

Talks:
Dinner: 6pm at Thai restaurant on 55th St, Hyde Park.


Abstracts:

1:30-2:30: Antonio Montalbán  -  U. of Chicago.
Title: When low information is no information.
Abstract: It is been conjectured that if a Boolean algebra has a low_n
  presentation, it has a computable presentation. We look at another
  class of structures where this behavior does occur, namely, the class
  of linear orderings with infinitely many descending cuts. This is
  joint work with Asher Kach and Joe Miller.

  We will also look at the atom relation of Boolean algebras. Here, we
  have that complete information implies high information. We show that
  every high_3 computably enumerable degree appears in the spectrum of
  the atom relation of any computable Boolean algebra with infinitely
  many atoms.

3:00-4:00: Logan Axon  -  U. of Notre Dame.
Title: Random closed sets and probability.
Abstract:   Barmpalias, Broadhead, Cenzer, Dashti, and Weber defined a notion of
  randomness for closed subsets of Cantor space by coding each infinite
  binary tree without dead ends as a ternary real. The set of paths
  through such a tree is said to be random if the ternary code for the
  tree is (Martin-Loef) random. Every closed set of Cantor space is the
  set of paths through a unique binary tree without dead ends and so we
  have a well founded definition of random closed set. Probability
  theorists, on the other hand, have defined a random closed set to be
  something quite different. A random closed set as defined in the
  literature of probability theory is a measurable map from a
  probability space to the space of closed sets of a topological space
  (where this space is equipped with the Fell topology and the
  corresponding Borel sigma-algebra). In particular a random closed set
  of Cantor space is simply a measurable map from any probability space
  to the space of closed sets of Cantor space.

  This talk addresses one way of reconciling these two notions of random
  closed set. First we use the probability theory framework to develop a
  measure-based theory of randomness for the space of closed sets of
  Cantor space. Then we show that random closed sets in the sense of
  Barmpalias et. al. are a specific example of randomness with respect
  to this new framework. To conclude we will look at some other examples
  of randomness for closed sets that arise from this framework.

4:30-5:30: Joe Miller  -  U. of Wisconsin.
Title: What good is always guessing wrong?
Abstract: We'll discuss connections between diagonally noncomputable functions and algorithmic randomness.