Midwest Computability Seminar

III


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 three 1-hour talks and a few hours to talk and collaborate with each other.  The seminar started in the fall of 2009.

DATE: Tuesday, February 3rd, 2009 
PLACE: Ryerson, University of Chicago.
1100 East 58th Street, Chicago, IL 60637.


Speakers:

Schedule:


Abstracts:

12:50 - 1:40: David Diamondstone - U. of Chicago.
Title: Two equivalent definitions of random closed sets
Abstract: There are two distinct definitions in the effective randomness literature of what constitutes a random closed set. One derives from the Galton-Watson process in probability theory. This definition was used by Bjoern Kjos-Hanssen in studying infinite subsets of random sets of integers. The other definition was introduced by Barmpalias, Brodhead, Cenzer, Dashti, and Weber in their paper, Algorithmic randomness of closed sets. We show that the random closed sets under the two definitions coincide, excepting the empty set. This follows from an effective version of the result that the distribution on trees introduced by Barmpalias at all is the same as the distribution of the extendible part of a Galton-Watson tree. (Joint work with Bjoern Kjos-Hanssen.)

2:10 - 3:00: Bart Kastermans - U. of Wisconsin.
Title: Generating Sets for Cofinitary Groups
Abstract: A subgroup of Sym(N) is cofinitary iff all elements other than the identity have finitely many fixed points.  A maximal cofinitary group is a cofinitary subgroup of Sym(N) not properly contained in a larger one.  The problem of determining the least possible complexity for maximal cofinitary groups has been open for a long time.  We will explain some of the results around that problem, and some of the questions it gives rise to.  We will focus on a computability theoretic result about generating a noncomputable cofinitary group from a uniformly computable sequence of generators.  For this result we will explain some of the ideas of how to prove it.

4:30 - 5:20: Richard Shore - Cornell Univeristy.
Title: A Direct Local Definition of the Turing Jump
Abstract: The issue of the definability of the Turing jump operator in terms of the relation of relative computability alone was raised already by Kleene and Post [1954] in the first paper on the structure of the Turning degrees $% \left\langle \mathcal{D}_{T},\leq _{T}\right\rangle $. It was proven to be definable by Shore and Slaman [1999] by a method that improved a theorem of Jockusch and Shore [1984] to convert an (as yet unpublished) definition of the double jump by Slaman and Woodin (see Slaman [2008]) to one of the jump itself. This proof of the definability of the double jump relied on metamathematical (absoluteness) and set theoretic (forcing) results and applied to the degrees as a whole but not to substructures. We will describe a direct (purely recursion theoretic) approach that proves that the Turing jump is definable in any downward closed subset of $\mathcal{D}$ that is closed under the jump and contains the degree $\mathbf{0}^{(\omega )}$. There are then many corollaries about definability in, and restrictions on possible automorphisms of, $\mathcal{D}$ and such jump ideals.



Previous Seminars: