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 WisconsinMadison. 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:

Reese Johnston  Wisconsin
 Rutger Kuyper  Wisconsin
 Mariya Soskova  Sofia University
 Mars Yamaleev  Kazan Federal University
Schedule:
 12:00  1:00: Lunch
 1:00  1:50: Rutger Kuyper
 2:30  3:00: Reese Johnston
 3:20  3:50: Mars Yamaleev
 4:30  5:20: Mariya Soskova
 6:00: Dinner at Chant,
1509 E. 53rd St.
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 Δ^{1}_{1} 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 longstanding 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_2statement alpha implies a second Pi^1_2statement beta over
EL_0, the intuitionistic version of RCA_0, plus Markov's principle, if and
only if beta Weihrauchreduces 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 MartinLöf tests, c.e. supermartingales, and
even prefixfree Kolmogorov complexity. When we relativize these
notions to an oracle X, we simply replace the c.e. objects with their
Xc.e. counterparts. In this talk we will explore a more general
method of relativization: instead of Xc.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 2c.e. degrees
Abstract: Given a 2computably enumerable (2c.e.) set D
with an effective
approximation {D_{s}}_{s ∈ ω} such that D_{s}D_{s1}
≤ 1, we say that L(D) = {s : ∃ x ∈ D_{s}  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 2c.e. Turing degree d, we define L[d] =
{ deg(L(B)) : B is 2c.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 2c.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
2c.e. degree.
In the talk we will review the recent results and discuss possible
approaches in distinguishing properly 2c.e. degrees from c.e.
degrees in the class of all 2c.e. degrees. Also we will consider
possible analogues L[d] for the case of wttdegrees and
their applications.
Previous Seminars:
 Sept 23rd 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 21st 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.
 Nov 1st 2011. Mingzhong Cai 
Chris Conidis  Stephen Flood 
Jeff Hirst  Asher Kach.
 Nov 15th 2012 Achilles Beros
 Rod Downey  Jesse Johnson  Sam Sanders  Steven VanDendriessche 
Matthew Wright.
 April 2nd 2013 Howard
Becker  Denis Hirschfeldt  Paul Schupp.
 October 1st 2013 Peter Cholak
 Mushfeq Khan  Victor OcasioGonzález  Jonathan Stephenson
 April 29th, 2014 Rod Downey 
Noam Greenberg  Gregory Igusa  Alexander Melnikov  Kyle Riggs
 September 30th, 2014 Eric Astor 
Quinn Culver  Jack Lutz  Timothy McNicholl
 February 17th, 2015 Carl Jockusch 
Julia Knight  Steffen Lempp
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.