Midwest Computability Seminar

XVII


The Midwest Computability Seminar is a joint venture between the University of Chicago, the University of Notre Dame, and the University of Wisconsin-Madison. It meets once or twice per semester at the University of Chicago, and is attended by faculty and students from these universities and others in the area. The seminar started in the fall of 2008.

DATE: Thursday, January 28, 2016.
PLACE: Ryerson Hall 352 (the Barn), The University of Chicago.
1100 East 58th Street, Chicago, IL 60637.


Speakers:

Schedule:


Abstracts:

Reese Johnston

Title: Degrees of isolated paths in trees of countable width

Abstract: In the setting of ω1-computability, isolated paths through computable binary trees can be very complex. It is easy to show that every such path must be Δ11 but no better upper bound is known. In this talk, I will present progress made towards showing that this is in fact the only upper bound; in particular, for α within a certain range much larger than the hyperarithmetic ordinals, there exists a computable tree of countable width in which the unique path computes 0(α).


Rutger Kuyper

Title: Weihrauch reducibility and reverse mathematics: two sides of the same coin?

Abstract: In this talk we will present a contribution to the recent interest in the intuitive similarity between reverse mathematics and Weihrauch reducibility. There are two main approaches to formalising this connection. The first of these proceeds by formalising Weihrauch reducibility within reverse mathematics, an approach which was pioneered by Dorais et al. and Dzhafarov. The other approach is to connect Weihrauch reducibility to intuitionistic reverse mathematics, building on the long-standing intuition that there is a tight connection between intuitionistic logic and computability. This field studying this connection goes under the name of realisability. Techniques from realisability have first been brought into the setting of reverse mathematics by Hirst and Mummert, whose work was continued by Dorais, and by Fujiwara, in their work on the reverse mathematical strength of sequential versions of theorems. We present a precise connection between Weihrauch reducibility and provability in intuitionistic reverse mathematics, building on the work of the authors mentioned in the previous paragraph. Roughly speaking, we show that a Pi^1_2-statement alpha implies a second Pi^1_2-statement beta over EL_0, the intuitionistic version of RCA_0, plus Markov's principle, if and only if beta Weihrauch-reduces to alpha. Of course, one quickly realises the theorem cannot be true as stated, but we give a precise way to state the theorem using the notion of composition in the Weihrauch degrees, and we also show that the statement just given holds if we restrict our intuitionistic calculus to an affine variant (i.e. a version which excludes some of the contraction rules in its sequent calculus).


Mariya Soskova

Title: Randomness relative to an enumeration oracle

Abstract: Many notions in effective randomness are defined in terms of c.e. objects. This includes Martin-Löf tests, c.e. supermartingales, and even prefix-free Kolmogorov complexity. When we relativize these notions to an oracle X, we simply replace the c.e. objects with their X-c.e. counterparts. In this talk we will explore a more general method of relativization: instead of X-c.e. objects we consider object that are enumeration reducible to X. We will investigate how much of the usual understanding of randomness can be preserved in this new setting and what breaks down. This is joint work with Joe Miller.


Mars Yamaleev

Title: Spectra of the Lachlan degrees of properly 2-c.e. degrees

Abstract: Given a 2-computably enumerable (2-c.e.) set D with an effective approximation {Ds}s ∈ ω such that |Ds-Ds-1| ≤ 1, we say that L(D) = {s : ∃ x ∈ Ds - D} is the Lachlan set of D. It is easy to show that the Turing degree of L(D) doesn't depend on the approximation (e.g., by Ishmukhametov [1999]), hence we say that deg(L(D)) is the Lachlan degree of D. Given a 2-c.e. Turing degree d, we define L[d] = { deg(L(B)) : B is 2-c.e and B ≡T D}, the spectrum of the Lachlan degrees of d. Clearly, elements of L[d] are c.e. degrees, moreover, for any w ∈ L[d] we have that w ≤ d and d is computably enumerable relative to w.

In the talk we will discuss spectra of the Lachlan degrees L[d] and their properties related to d. It is easy to see that L[d] = [0,d] if and only if d has a c.e. degree. Also it is easy to see that 0, d ∉ L[d] for any properly 2-c.e. degree d. More specialized results were obtained by Ishmukhametov [1999,2000], and our recent results (jointly with Liu, Fang and Wu) are their logical continuation. For example, we obtain that L[d] cannot contain a minimal pair of c.e. degrees if d is a properly 2-c.e. degree.

In the talk we will review the recent results and discuss possible approaches in distinguishing properly 2-c.e. degrees from c.e. degrees in the class of all 2-c.e. degrees. Also we will consider possible analogues L[d] for the case of wtt-degrees and their applications.

Previous Seminars:

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