## IX

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 half hour talks and 1-hour talks, though this varies, and a few hours to talk and collaborate with each other.  The seminar started in the fall of 2008.

DATE
: Tuesday, February 15, 2011.
PLACE: Ryerson, University of Chicago.
1100 East 58th Street, Chicago, IL 60637.

Speakers:

• Uri Andrews - U. of Wisconsin.
• Paola D'Aquino - U. di Napoli
• David Diamondstone - U. of Chicago
• Christopher Porter - U. of Notre Dame.
• Rebecca Steiner - City U. of NY

#### Schedule:

• 12:00 - 1:00: Lunch. (the Barn Ry 352)
• 1:00 - 1:30: Rebecca Steiner.
• 1:35 - 2:05: Paola D'Aquino.
• 2:30 - 3:00: Uri Andrews.
• 2:30 - 3:30: Coffee break - Move to Eckhart 206 at 3:30.
• 3:50- 4:20: Christopher Porter.
• 4:30 - 5:00: David Diamondstone.
• 6:00: The Nile - 1611 East 55th Street, Chicago, IL 60615-5803

#### Abstracts:

Rebecca Steiner.
Title: Computable Fields and the Bounded Turing Reduction
Abstract: For a computable field F, the splitting set S_F of F is the set of polynomials with coefficients in F which factor over F, and the root set  R_F of F is the set of polynomials with coefficients in F which have a root in F.
Results of Frohlich and Shepherdson from 1956 imply that for a computable field F, the splitting set S_F and the root set R_F are Turing-equivalent.  Much more recently, R. G. Miller showed that for algebraic fields, the root set actually has slightly higher complexity: for algebraic fields F, it is always the case that S_F 1-reduces to R_F, but there are algebraic fields F where we have R_F not 1-reducible to S_F.
Here we compare the splitting set and the root set of a computable algebraic field under a different reduction: the bounded Turing reduction.  We construct a computable algebraic field for which R_F does not bT-reduce to S_F.
We also define a Rabin embedding g of a field into its algebraic closure, and for a computable algebraic field F, we compare the relative complexities of R_F, S_F, and g(F) under m-reducibility and under bT-reducibility.

Paola D'Aquino.
Title: Schuanuel's Conjecture and exponential fields
Abstract: I will analyze some consequences of Schanuel's Conjecture over exponential fields, in connection also to the model theoretic analysis of the complex exponential field proposed by Zilber.

Christopher Porter.
Title: Randomness, Learnability, and Depth
Abstract: In this talk, I will discuss recent work relating randomness-theoretic notions of learning developed by C.P. Schnorr and his student Peter Fuchs in the late 1970s to Charles Bennett's notion of logical depth.

Uri Andrews.
Abstact: (joint work with Steffen Lempp and Selwyn Ng) We say that a set $A$ is enumeration below ($\leq_e$) a set $B$ if there is an effective procedure to turn an enumeration of $B$ into an enumeration of $A$. We examine the structure of the enumeration degrees of $\Sigma_2$ sets. Slaman and Woodin showed that the 5-quantifier theory of this structure is undecidable, and Kent improved this to show that the 3-quantifier theory is undecidable. The embedding of the Turing degrees into the enumeration degrees ($A \mapsto A\oplus \bar{A}$) gives that the 1-quantifier theory is decidable. This talk will discuss recent work towards understanding the 2-quantifier theory of the enumeration degrees.
A pair of degrees $(a,b)$ form an Ahmad pair if $a\nleq b$ and $c< a \rightarrow c<b$. In her thesis, Ahmad showed that Ahmad pairs exist, and that no symmetric Ahmad pair exists (ie: $(a,b)$ an Ahmad pair and $(b,a)$ an Ahmad pair). We consider generalizations of this symmetric Ahmad phenomenon of the form $a_1,\ldots a_n$ an anti-chain such that $c<a_i \rightarrow \exists j \neq i c<a_j$, and show that such tuples do not exist.

David Diamondstone.
Title: Promptness and cupping for $\leq_{wtt}$
Abstract: In 1984, Ambos-Spies, Jockusch, Shore, and Soare proved that among the Turing degrees, the degrees of promptly simple sets coincide with the degrees which are low-cuppable. Andr\'{e} Nies asked whether the same is true for sets which are superlow cuppable, and in 2008 I demonstrated that this is not the case. The question then naturally arose whether being superlow cuppable is equivalent to some stronger notion of promptness. Ng Keng Meng and I introduce a new notion, which we call strong promptness, which implies superlow cuppability and gives something akin to the prompt = low-cuppable equivalence for weak truth-table reducibility.
(joint work with Ng Keng Meng)

##### 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.

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.