Midwest Computability Seminar

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:

Schedule:

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.
Title: (Ah)madness.
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:
   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.