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:
-
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 Δ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:
- 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 Ocasio-Gonzá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.