BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Theodore Slaman (UC Berkeley)
DTSTART;VALUE=DATE-TIME:20200421T140000Z
DTEND;VALUE=DATE-TIME:20200421T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/1
DESCRIPTION:Title: Recu
rsion Theory and Diophantine Approximation\nby Theodore Slaman (UC Ber
keley) as part of Computability theory and applications\n\n\nAbstract\nWe
will give a survey of some connections between Recursion Theory\, especial
ly Algorithmic Randomness\, and Diophantine Approximation\, especially nor
mality and exponents of irrationality. We will emphasize what we view as
the contribution of a recursion theoretic perspective.\n
LOCATION:https://researchseminars.org/talk/CTA/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julia Knight (Notre Dame)
DTSTART;VALUE=DATE-TIME:20200428T120000Z
DTEND;VALUE=DATE-TIME:20200428T130000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/2
DESCRIPTION:Title: Limi
ting Density and Free Structures\nby Julia Knight (Notre Dame) as part
of Computability theory and applications\n\n\nAbstract\nGromov had asked
what a random group looks like - in a limiting density sense. I conjecture
d that the elementary frst order theory of the random group on n >= 2 gene
rators\, and with a single relator matches\nthat of the non-Abelian free g
roups. Coulon\, Ho\, and Logan have proved that the theories match on univ
ersal sentences. We may ask Gromovs question for other varieties. Franklin
and I looked for varieties for which\ncalculating the limiting densities
is easier. We have examples for which the elementary frst order theory of
the random structure matches that of the free structure\, and other exampl
es for which the theories differ.\n(joint work with Johanna Franklin)\n
LOCATION:https://researchseminars.org/talk/CTA/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marta Fiori Carones (LMU Munich)
DTSTART;VALUE=DATE-TIME:20200505T200000Z
DTEND;VALUE=DATE-TIME:20200505T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/3
DESCRIPTION:Title: A th
eorem from Rival and Sands and reverse mathematics\nby Marta Fiori Car
ones (LMU Munich) as part of Computability theory and applications\n\n\nAb
stract\nIn 1980 Ivan Rival and Bill Sands proved that for each infinite po
set P with finite width (i.e. such that there is a fixed finite bound on t
he size of antichains in P) there is an infinite chain C ⊆ P such that e
ach element of P is comparable to none or to infinitely many elements of
C. Moreover\, if P is countable\, C can be found such that each element of
P is comparable to none or to cofinitely many elements of C.\nWe prove t
hat some versions of the previous theorem are equivalent to the Ascending/
descending sequence principle or to related known principles of the revers
e mathematics zoo. \n(Joint work with Alberto Marcone\, Paul Shafer and Gi
ovanni Soldà)\n
LOCATION:https://researchseminars.org/talk/CTA/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Denis Hirschfeldt (University of Chicago)
DTSTART;VALUE=DATE-TIME:20200519T200000Z
DTEND;VALUE=DATE-TIME:20200519T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/4
DESCRIPTION:Title: Mini
mal pairs in the generic degrees\nby Denis Hirschfeldt (University of
Chicago) as part of Computability theory and applications\n\n\nAbstract\nG
eneric computability is a notion of "almost everywhere computability" that
has been studied from a computability-theoretic perspective by several au
thors following work of Jockusch and Schupp. It leads naturally to a notio
n of reducibility\, and hence to a degree structure. I will discuss the co
nstruction of a minimal pair in the generic degrees\, which contrasts with
Igusa's result that there are\nno minimal pairs for the similar notion of
relative generic computability. I will then focus on several related ques
tions that remain open.\n
LOCATION:https://researchseminars.org/talk/CTA/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Harrison-Trainor (Victoria University of Wellington\, New
Zealand)
DTSTART;VALUE=DATE-TIME:20200513T010000Z
DTEND;VALUE=DATE-TIME:20200513T020000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/5
DESCRIPTION:Title: The
tree of tuples of a structure\nby Matthew Harrison-Trainor (Victoria U
niversity of Wellington\, New Zealand) as part of Computability theory and
applications\n\n\nAbstract\nGiven a countable structure\, one can associa
te a tree of finite tuples from that structure\, with each tuple labeled b
y its atomic type. This tree encodes the back-and-forth information of the
structure\, and hence determines the isomorphism type\, but it is still m
issing something: with Montalban I proved that there are structures which
cannot be computably (or even hyperarithmetically) recovered from their tr
ee of tuples. I'll explain the meaning of this result by exploring two sep
arate threads in computable structure theory: universality and coding.\n
LOCATION:https://researchseminars.org/talk/CTA/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dan Turetsky (Victoria University of Wellington\, New Zealand)
DTSTART;VALUE=DATE-TIME:20200527T010000Z
DTEND;VALUE=DATE-TIME:20200527T020000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/6
DESCRIPTION:Title: Codi
ng in the automorphism group of a structure\nby Dan Turetsky (Victoria
University of Wellington\, New Zealand) as part of Computability theory a
nd applications\n\n\nAbstract\nIn this talk I will discuss a new technique
for coding a closed set into the automorphism group of a structure. This
technique has applications to problems in Scott rank\, effective dimensio
n\, and degrees of categoricity. For instance\, I will explain how it can
be used to construct a computably categorical structure with noncomputabl
e Scott rank.\n
LOCATION:https://researchseminars.org/talk/CTA/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vittorio Bard (Università degli Studi di Torino)
DTSTART;VALUE=DATE-TIME:20200602T140000Z
DTEND;VALUE=DATE-TIME:20200602T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/7
DESCRIPTION:Title: A lo
cal approach towards uniform Martin’s conjecture\nby Vittorio Bard (
Università degli Studi di Torino) as part of Computability theory and app
lications\n\n\nAbstract\nIn 1967 Sacks asked whether there is degree invar
iant r.e. operator that maps x to a solution to Post's problem relativized
for x. In 1975\, Lachlan proved that the answer is no if we require the o
perator to be degree invariant in a uniform way.\nSack's question can be c
onsidered the forefather of Martin's conjecture\, a foundamental open prob
lem that hypothizes that degree invariant functions under AD have limited
possibilities of behavior. Following Lachlan's example\, in the late 80s S
laman and Steel proved Martin's conjecture for unifromly degree invariant
functions.\nWe will show that half of this result is actually the conseque
nce of phenomena that unifromly degree invariant functions already manisfe
st on single Turing degrees. We also present a joint result with Patrick L
utz\, in which we show that Lachlan's result arises locally\, too.\n
LOCATION:https://researchseminars.org/talk/CTA/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nikolai Bazhenov (Sobolev Institute of Mathematics)
DTSTART;VALUE=DATE-TIME:20200609T140000Z
DTEND;VALUE=DATE-TIME:20200609T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/8
DESCRIPTION:Title: Roge
rs semilattices in the analytical hierarchy\nby Nikolai Bazhenov (Sobo
lev Institute of Mathematics) as part of Computability theory and applicat
ions\n\n\nAbstract\nFor a countable set S\, a numbering of S is a surjecti
ve map from ω onto S. A numbering ν is reducible to a numbering μ if th
ere is a computable function f such that ν(x) = μ f(x) for all indices x
. The notion of reducibility between numberings gives rise to a class of u
pper semilattices\, which are usually called Rogers semilattices. We discu
ss recent results on Rogers semilattices induced by numberings in the anal
ytical hierarchy. Special attention is given to the first-order properties
of Rogers semilattices. The talk is based on joint works with Manat Musta
fa\, Sergei Ospichev\, and Mars Yamaleev.\n
LOCATION:https://researchseminars.org/talk/CTA/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lu Liu (Central South University)
DTSTART;VALUE=DATE-TIME:20200617T010000Z
DTEND;VALUE=DATE-TIME:20200617T020000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/9
DESCRIPTION:Title: The
coding power of products of partitions\nby Lu Liu (Central South Unive
rsity) as part of Computability theory and applications\n\n\nAbstract\nGiv
en two combinatorial notions P0 and P1\, can we encode P0 via P1. In this
talk we address the question where P0 is a 3-partition of integers and P1
is a product of finitely many 2-partitions of integers.\n We firstly
reduce the question to a lemma which asserts that certain Pi01 class of p
artitions admit two members violating a particular combinatorial constrain
t. Then we took a digression to see how complex does the class has to be s
o as to maintain the cross constraint. \n On the other hand\, reducin
g the complexity of the two members in the lemma in certain ways will ans
wer an open question concerning a sort of Weihrauch degree of stable Ramse
y's theorem for pairs. It turns out the resulted strengthen of the lemma i
s a basis theorem for Pi01 class with additional constraint. We look at se
veral such variants of basis theorem\, among them some are unknown. \n
We end up by introducing some results and questions concerning product
of infinitely many partitions.\n
LOCATION:https://researchseminars.org/talk/CTA/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sarah Reitzes (University of Chicago)
DTSTART;VALUE=DATE-TIME:20200623T200000Z
DTEND;VALUE=DATE-TIME:20200623T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/10
DESCRIPTION:Title: Red
uction games\, provability\, and compactness\nby Sarah Reitzes (Univer
sity of Chicago) as part of Computability theory and applications\n\n\nAbs
tract\nIn this talk\, I will discuss joint work with Damir D. Dzhafarov an
d Denis R. Hirschfeldt. Our work centers on the characterization of proble
ms P and Q such that P is omega-reducible to Q\, as well as problems\n P a
nd Q such that RCA_0 proves Q implies P\, in terms of winning strategies i
n certain games. These characterizations were originally introduced by Hir
schfeldt and Jockusch. I will discuss extensions and generalizations of th
ese characterizations\, including\n a certain notion of compactness that a
llows us\, for strategies satisfying particular conditions\, to bound the
number of moves it takes to win. This bound is independent of the instance
of the problem P being considered.\n
LOCATION:https://researchseminars.org/talk/CTA/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rod Downey (Victoria University of Wellington)
DTSTART;VALUE=DATE-TIME:20200708T010000Z
DTEND;VALUE=DATE-TIME:20200708T020000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/11
DESCRIPTION:Title: Sac
ks' Splitting Theorem Re-examined (again)\nby Rod Downey (Victoria Uni
versity of Wellington) as part of Computability theory and applications\n\
nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CTA/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mariya Soskova (University of Wisconsin-Madison)
DTSTART;VALUE=DATE-TIME:20200714T200000Z
DTEND;VALUE=DATE-TIME:20200714T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/12
DESCRIPTION:Title: PA
relative to an enumeration oracle\nby Mariya Soskova (University of Wi
sconsin-Madison) as part of Computability theory and applications\n\nAbstr
act: TBA\n
LOCATION:https://researchseminars.org/talk/CTA/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Amaury Pouly (CNRS)
DTSTART;VALUE=DATE-TIME:20200630T140000Z
DTEND;VALUE=DATE-TIME:20200630T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/13
DESCRIPTION:Title: A S
urvey on Analog Models of Computation\nby Amaury Pouly (CNRS) as part
of Computability theory and applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CTA/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cristóbal Rojas (Universidad Andrés Bello)
DTSTART;VALUE=DATE-TIME:20200721T150000Z
DTEND;VALUE=DATE-TIME:20200721T160000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/14
DESCRIPTION:Title: Sta
tistical Chaos — a new barrier in the prediction/simulation of physical
systems\nby Cristóbal Rojas (Universidad Andrés Bello) as part of Co
mputability theory and applications\n\n\nAbstract\nIt is well known that f
or systems exhibiting “sensitivity to initial conditions”\, it is prac
tically impossible to predict individual trajectories beyond a very limite
d time horizon. To overcome this difficulty\, a statistical approach was
developed -- while the computed trajectories are not individually meaningf
ul\, when regarded as an ensemble\, their average represents a statistical
distribution that can be used to make meaningful probabilistic prediction
s about the system. This statistical paradigm is ubiquitous in modern appl
ications. In this talk we present a new obstacle in applying the statisti
cal approach. We show that the statistical behavior of a parametrized syst
em may exhibit “sensitivity to parameters”\, and that this may lead to
non computability of the limiting\, meaningful\, statistical distribution
. We will explain all this in the simplest nonlinear class of systems: qua
dratic maps of the interval [0\,1]. This is joint work with M. Yampolsky.\
n
LOCATION:https://researchseminars.org/talk/CTA/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrew Marks (UCLA)
DTSTART;VALUE=DATE-TIME:20200728T210000Z
DTEND;VALUE=DATE-TIME:20200728T220000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/15
DESCRIPTION:Title: Pri
ority arguments in descriptive set theory\nby Andrew Marks (UCLA) as p
art of Computability theory and applications\n\n\nAbstract\nWe give a new
characterization of when a Borel set is\nSigma^0_n complete for n at at le
ast 3. This characterization is\nproved using Antonio Montalb\\'an's true
stages machinery for\nconducting priority arguments.\n\nAs an application\
, we prove the decomposability conjecture in\ndescriptive set theory assum
ing projective determinacy. This\nconjecture characterizes precisely which
Borel functions are\ndecomposable into a countable union of continuous fu
nctions with\n$\\Pi^0_n$ domains. Our proof also uses a theorem of Leo Har
rington\nthat assuming the axiom of determinacy there is no $\\omega_1$ le
ngth\nsequence of distinct Borel sets of bounded rank. This is joint work\
nwith Adam Day.\n
LOCATION:https://researchseminars.org/talk/CTA/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benoit Monin (LACL/Créteil University)
DTSTART;VALUE=DATE-TIME:20200804T140000Z
DTEND;VALUE=DATE-TIME:20200804T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/16
DESCRIPTION:Title: Gen
ericity and randomness with ITTMs\nby Benoit Monin (LACL/Créteil Univ
ersity) as part of Computability theory and applications\n\n\nAbstract\nWe
will talk about constructibility through the study of Infinite-Time Turin
g machines. The study of Infinite-Time Turing machines\, ITTMs for short\,
goes back to a paper by Hamkins and Lewis. Informally these machines work
like regular Turing machines\, with in addition that the time of computat
ion can be any ordinal. Special rules are then defined to specify what hap
pens at a limit step of computation. \n\nThis simple computational model y
ields several new non-trivial classes of objects\, the first one being the
class of objects which are computable using some ITTM. These classes have
been later well understood and characterized by Welch. ITTMs are not the
first attempt of extending computability notions. This was done previously
for instance with alpha-recursion theory\, an extension of recursion theo
ry to Sigma_1-definability of subsets of ordinals\, within initial segment
s of the Godel constructible hierarchy. Even though alpha-recursion theory
is defined in a rather abstract way\, the specialists have a good intuiti
on of what ``compute'' means in this setting\, and this intuition relies o
n the rough idea of ``some'' informal machine carrying computation times t
hrough the ordinal. ITTMs appeared all the more interesting\, as they cons
ist of a precise machine model that corresponds to part of alpha-recursion
theory.\n\nRecently Carl and Schlicht used the ITTM model to extend algor
ithmic randomness and effective genericity notions in this setting. Generi
city and randomness are two different approaches to study typical objects\
, that is\, objects having ``all the typical properties'' for some notion
of typicality. For randomness\, a property is typical if the class of real
s sharing it is of measure 1\, whereas for genericity\, a property is typi
cal if the class of reals sharing it is co-meager.\n\nWe will present a ge
neral framework to study randomness and genericity within Godel's construc
tible hierarchy. Using this framework\, we will present various theorems a
bout randomness and genericity with respect to ITTMs. We will then end wit
h a few exciting open questions for which we believe Beller Jensen and Wel
ch's forcing technique of their book ``coding the universe'' should be use
ful.\n
LOCATION:https://researchseminars.org/talk/CTA/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jun Le Goh (University of Wisconsin)
DTSTART;VALUE=DATE-TIME:20200811T140000Z
DTEND;VALUE=DATE-TIME:20200811T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/17
DESCRIPTION:Title: Com
puting descending sequences in linear orderings\nby Jun Le Goh (Univer
sity of Wisconsin) as part of Computability theory and applications\n\n\nA
bstract\nLet DS be the problem of computing a descending sequence in a giv
en ill-founded linear ordering. We investigate the uniform computational c
ontent of DS from the point of view of Weihrauch reducibility\, in particu
lar its relationship with the analogous problem of computing a path in a g
iven ill-founded tree (known as choice on Baire space).\n\nFirst\, we show
that DS is strictly Weihrauch reducible to choice on Baire space. Our tec
hniques characterize the problems which have codomain N and are Weihrauch
reducible to DS\, thereby identifying the so-called first-order part of DS
.\n\nSecond\, we use the technique of inseparable $\\Pi^1_1$ sets (first u
sed by Angles d'Auriac\, Kihara in this context) to study the strengthenin
g of DS whose inputs are $\\Sigma^1_1$-codes for ill-founded linear orderi
ngs. We prove that this strengthening is still strictly Weihrauch reducibl
e to choice on Baire space.\n\nThis is joint work with Arno Pauly and Manl
io Valenti.\n
LOCATION:https://researchseminars.org/talk/CTA/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joe Miller (University of Wisconsin)
DTSTART;VALUE=DATE-TIME:20200818T200000Z
DTEND;VALUE=DATE-TIME:20200818T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/18
DESCRIPTION:Title: Red
undancy of information: lowering effective dimension\nby Joe Miller (U
niversity of Wisconsin) as part of Computability theory and applications\n
\n\nAbstract\nA natural way to measure the similarity between two infinite
\nbinary sequences X and Y is to take the (upper) density of their\nsymmet
ric difference. This is the Besicovitch distance on Cantor\nspace. If d(X\
,Y) = 0\, then we say that X and Y are coarsely\nequivalent. Greenberg\, M
.\, Shen\, and Westrick (2018) proved that a\nbinary sequence has effectiv
e (Hausdorff) dimension 1 if and only if\nit is coarsely equivalent to a M
artin-Löf random sequence. They went\non to determine the best and worst
cases for the distance from a\ndimension t sequence to the nearest dimensi
on s>t sequence. Thus\, the\ndifficulty of increasing dimension is underst
ood.\n\nGreenberg\, et al. also determined the distance from a dimension 1
\nsequence to the nearest dimension t sequence. But they left open the\nge
neral problem of reducing dimension\, which is made difficult by the\nfact
that the information in a dimension s sequence can be coded (at\nleast so
mewhat) redundantly. Goh\, M.\, Soskova\, and Westrick recently\ngave a co
mplete solution.\n\nI will talk about both the results in the 2018 paper a
nd the more\nrecent work. In particular\, I will discuss some of the codin
g theory\nbehind these results. No previous knowledge of coding theory is\
nassumed.\n
LOCATION:https://researchseminars.org/talk/CTA/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andre Nies (University of Auckland)
DTSTART;VALUE=DATE-TIME:20200826T010000Z
DTEND;VALUE=DATE-TIME:20200826T020000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/19
DESCRIPTION:Title: Dis
covering structure within the class of K-trivial sets\nby Andre Nies (
University of Auckland) as part of Computability theory and applications\n
\n\nAbstract\nJoint work with Noam Greenberg\, Joseph Miller\, and Dan Tur
etsky\n\nThe K-trivial sets are antirandom in the sense that the initial s
egment complexity in terms of prefix-free Kolmogorov complexity K grows as
slowly as possible. Chaitin introduced this notion in about 1975\, and sh
owed that each K-trivial is Turing below the halting set. Shortly after\,
Solovay proved that a K-trivial set can be noncomputable. \n\nIn the pas
t two decades\, many alternative characterisations of this class have been
found: properties such as being low for K\, low for Martin-Löf (ML) ra
ndomness\, and a basis for ML randomness\, which state in one way or the
other that the set is close to computable. \n\nInitially\, the class of
noncomputable K-trivials appeared to be amorphous. More recently\, eviden
ce of an internal structure has been found. Most of these results can be p
hrased in the language of a mysterious reducibility on the K-trivials whi
ch is weaker than Turing’s: A is ML-below B if each ML-random computing
B also computes A.\n\nBienvenu\, Greenberg\, Kucera\, Nies and Turetsky (J
EMS 2016) showed that there an ML complete K-trivial set. Greenberg\, Mill
er and Nies (JML\, 2019) established a dense hierarchy of subclasses o
f the K-trivials based on fragments of Omega computing the set\, and each
such subclass is an initial segment for ML. More recent results generali
se these approaches using cost functions. They also show that each K-trivi
al set is ML-equivalent to a c.e. K-trivial. \n\nThe extreme lowness of K
-trivials\, far from being an obstacle\, allows for methods which don’t
work in a wider setting. The talk provides an overview and discusses ope
n questions. For instance\, is ML-completeness an arithmetical property of
K-trivials?\n
LOCATION:https://researchseminars.org/talk/CTA/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Patrick Lutz (UC Berkeley)
DTSTART;VALUE=DATE-TIME:20200901T200000Z
DTEND;VALUE=DATE-TIME:20200901T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/20
DESCRIPTION:Title: Par
t 1 of Martin's Conjecture for Order Preserving Functions\nby Patrick
Lutz (UC Berkeley) as part of Computability theory and applications\n\n\nA
bstract\nMartin's conjecture is an attempt to make precise the idea that t
he only natural functions on the Turing degrees are the constant functions
\, the identity\, and transfinite iterates of the Turing jump. The conject
ure is typically divided into two parts. Very roughly\, the first part sta
tes that every natural function on the Turing degrees is either eventually
constant or eventually increasing and the second part states that the nat
ural functions which are increasing form a well-order under eventual domin
ation\, where the successor operation in this well-order is the Turing jum
p. \n\nIn the 1980's\, Slaman and Steel proved that the second part of Mar
tin's conjecture holds for order-preserving Borel functions. In joint work
with Benny Siskind\, we prove the complementary result that (assuming ana
lytic determinacy) the first part of the conjecture also holds for order-p
reserving Borel functions (and under AD\, for all order-preserving functio
ns). Our methods also yield several other new results\, including an equiv
alence between the first part of Martin's conjecture and a statement about
the Rudin-Keisler order on ultrafilters on the Turing degrees. \n\nIn my
talk\, I will give an overview of Martin's conjecture and then describe ou
r new results.\n
LOCATION:https://researchseminars.org/talk/CTA/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Patrick Uftring (TU Darmstadt)
DTSTART;VALUE=DATE-TIME:20200908T140000Z
DTEND;VALUE=DATE-TIME:20200908T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/21
DESCRIPTION:Title: The
characterization of Weihrauch reducibility in systems containing $E$-$PA^
\\omega$ + $QF$-$AC^{0\,0}$\nby Patrick Uftring (TU Darmstadt) as part
of Computability theory and applications\n\n\nAbstract\nWe characterize W
eihrauch reducibility in E-PAω + QF-AC0\,0 and all systems containing it
by the provability in a linear variant of the same calculus using modifica
tions of Gödel's Dialectica interpretation that incorporate ideas from li
near logic\, nonstandard arithmetic\, higher-order computability\, and pha
se semantics. A full preprint is available here: https://arxiv.org/abs/20
03.13331\n
LOCATION:https://researchseminars.org/talk/CTA/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alberto Marcone (Università di Udine)
DTSTART;VALUE=DATE-TIME:20200915T130000Z
DTEND;VALUE=DATE-TIME:20200915T140000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/22
DESCRIPTION:Title: The
higher levels of the Weihrauch lattice\nby Alberto Marcone (Universit
à di Udine) as part of Computability theory and applications\n\n\nAbstrac
t\nThe classification of mathematical problems in the Weihrauch lattice is
a line of research that blossomed in the last few years. Initially this a
pproach dealt mainly with statements which are provable in ACA_0 and showe
d that usually Weihrauch reducibility is more fine-grained than reverse ma
thematics.\n\nIn the last few years the study of multi-valued functions ar
ising from statements laying at higher levels (such as ATR_0 and Pi^1_1-CA
_0) of the reverse mathematics spectrum started as well. The multi-valued
functions studied so far include those arising from the perfect tree theor
em\, comparability of well-orders\, determinacy of open and clopen games\
, König’s duality theorem\, various forms of choice\, the open and clop
en Ramsey theorem and the Cantor-Bendixson theorem.\n\nAt this level often
a single theorem naturally leads to several multi-valued functions of dif
ferent Weihrauch degree\, depending on how the theorem is "read" from a co
mputability viewpoint. A case in point is the perfect tree theorem: it can
be read as the request to produce a perfect subtree of a tree with uncoun
tably many paths\, or as the request to list all paths of a tree which doe
s not contain a perfect subtree. Similarly\, the clopen Ramsey theorem lea
ds to the multi-valued function that associates to every clopen subset of
[N]^N an infinite homogeneous set on either side\, and to the multi-valued
function producing for each clopen subset which has an infinite homogeneo
us sets on one side a homogeneous set on that side. Similar functions can
be defined similarly starting from the open Ramsey theorem.\n\nIn this tal
k I discuss some of these results\, emphasizing recent joint work with my
students Vittorio Cipriani and Manlio Valenti.\n
LOCATION:https://researchseminars.org/talk/CTA/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Justine Miller (University of Notre Dame)
DTSTART;VALUE=DATE-TIME:20200915T200000Z
DTEND;VALUE=DATE-TIME:20200915T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/23
DESCRIPTION:Title: Non
computable Coding\, Density\, and Stochasticity\nby Justine Miller (Un
iversity of Notre Dame) as part of Computability theory and applications\n
\n\nAbstract\nWe introduce the into and within set operations in order to
construct sets of arbitrary intrinsic density from any Martin-Löf random.
We then show that these operations are useful more generally for working
with other notions of density as well\, in particular for viewing Church a
nd MWC stochasticity as a form of density.\n
LOCATION:https://researchseminars.org/talk/CTA/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christopher Porter (Drake University)
DTSTART;VALUE=DATE-TIME:20200929T200000Z
DTEND;VALUE=DATE-TIME:20200929T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/24
DESCRIPTION:Title: Eff
ective Dimension and the Intersection of Random Closed Sets\nby Christ
opher Porter (Drake University) as part of Computability theory and applic
ations\n\n\nAbstract\nThe connection between the effective dimension of se
quences and membership in algorithmically random closed subsets of Cantor
space was first identified by Diamondstone and Kjos-Hanssen. In this talk\
, I highlight joint work with Adam Case in which we extend Diamondstone an
d Kjos-Hanssen's result by identifying a relationship between the effectiv
e dimension of a sequence and what we refer to as the degree of intersecta
bility of certain families of random closed sets (also drawing on work by
Cenzer and Weber on the intersections of random closed sets). As we show\,
(1) the number of relatively random closed sets that can have a non-empty
intersection varies depending on the choice of underlying probability mea
sure on the space of closed subsets of Cantor space---this number being th
e degree of intersectability of a given family of random closed sets---and
(2) the effective dimension of a sequence X is inversely proportional to
the minimum degree of intersectability of a family of random closed sets\,
at least one of which contains X as a member. Put more simply\, a sequenc
e of lower dimension can only be in random closed sets with more branching
\, which are thus more intersectable\, whereas higher dimension sequences
can be in random closed sets with less branching\, which are thus less int
ersectable\, and the relationship between these two quantities (that is\,
effective dimension and degree of intersectability) can be given explicitl
y.\n
LOCATION:https://researchseminars.org/talk/CTA/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Leszek Kołodziejczyk (University of Warsaw)
DTSTART;VALUE=DATE-TIME:20201013T200000Z
DTEND;VALUE=DATE-TIME:20201013T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/25
DESCRIPTION:Title: Rev
erse mathematics of combinatorial principles over a weak base theory\n
by Leszek Kołodziejczyk (University of Warsaw) as part of Computability t
heory and applications\n\n\nAbstract\nReverse mathematics studies the stre
ngth of axioms needed to prove various\nmathematical theorems. Often\, the
theorems have the form $\\forall X \\exists\nY \\psi(X\,Y)$ with $X\, Y$
denoting subsets of $\\mathbb{N}$ and $\\psi$\narithmetical\, and the logi
cal strength required to prove them is closely\nrelated to the difficulty
of computing $Y$ given $X$. In the early decades\nof reverse mathematics\,
most of the theorems studied turned out to be\nequivalent\, over a relati
vely weak base theory\, to one of just a few typical\naxioms\, which are t
hemselves linearly ordered in terms of strength. More\nrecently\, however\
, many statements from combinatorics\, especially Ramsey\ntheory\, have be
en shown to be pairwise inequivalent or even logically\nincomparable.\n\nT
he usual base theory used in reverse mathematics is $\\mathrm{RCA}_0$\, wh
ich\nis intended to correspond roughly to the idea of "computable mathemat
ics".\nThe main two axioms of $\\mathrm{RCA}_0$ are: comprehension for com
putable\nproperties of natural numbers and mathematical induction for c.e.
\nproperties. A weaker theory in which induction for c.e. properties is\nr
eplaced by induction for computable properties has also been introduced\,\
nbut it has received much less attention. In the reverse mathematics\nlite
rature\, this weaker theory is known as $\\mathrm{RCA}^*_0$.\n\nIn this ta
lk\, I will discuss some results concerning the reverse mathematics\nof co
mbinatorial principles over $\\mathrm{RCA}^*_0$. We will focus mostly on\n
Ramsey's theorem and some of its well-known special cases: the\nchain-anti
chain principle CAC\, the ascending-descending chain principle ADS\,\nand
the cohesiveness principle COH.\n\nThe results I will talk about are part
of a larger project joint with Marta\nFiori Carones\, Katarzyna Kowalik\,
Tin Lok Wong\, and Keita Yokoyama.\n
LOCATION:https://researchseminars.org/talk/CTA/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Li Ling Ko (University of Notre Dame)
DTSTART;VALUE=DATE-TIME:20201027T200000Z
DTEND;VALUE=DATE-TIME:20201027T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/26
DESCRIPTION:Title: Fic
kleness and bounding lattices in the recursively enumerable Turing degrees
\nby Li Ling Ko (University of Notre Dame) as part of Computability th
eory and applications\n\n\nAbstract\nThe ability for a recursively enumera
ble Turing degree $d$ to bound certain\nimportant lattices depends on the
degree's fickleness. For instance\, $d$\nbounds $L_7$ (1-3-1) if and only
if $d$'s fickleness is $>\\omega$\n($\\geq\\omega^\\omega$). We work towar
ds finding a lattice that characterizes\nthe $>\\omega^2$ levels of fickle
ness and seek to understand the challenges\nfaced in finding such a lattic
e. The candidate lattices considered include\nthose that are generated fro
m three independent points\, and upper\nsemilattices that are obtained by
removing the meets from important\nlattices.\n
LOCATION:https://researchseminars.org/talk/CTA/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Paul Shafer (University of Leeds)
DTSTART;VALUE=DATE-TIME:20201110T210000Z
DTEND;VALUE=DATE-TIME:20201110T220000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/27
DESCRIPTION:Title: Ran
domness notions and reverse mathematics\nby Paul Shafer (University of
Leeds) as part of Computability theory and applications\n\n\nAbstract\nTh
ere are many notions of algorithmic randomness in addition to classic Mart
in-Löf randomness\, such as 2-randomness\, weak 2-randomness\, computable
randomness\, and Schnorr randomness. For each notion of randomness\, we
consider the statement "For every set Z\, there is a set X that is random
relative to Z" as a set-existence principle in second-order arithmetic\, a
nd we compare the strengths of these principles. We also show that a well
-known characterization of 2-randomness in terms of incompressibility can
be proved in RCA_0\, which is non-trivial because it requires avoiding the
use of $\\Sigma^0_2$ bounding.\n
LOCATION:https://researchseminars.org/talk/CTA/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Karen Lange (Wellesley College)
DTSTART;VALUE=DATE-TIME:20201124T210000Z
DTEND;VALUE=DATE-TIME:20201124T220000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/28
DESCRIPTION:Title: Com
plexity of root-taking in power series fields & related problems\nby K
aren Lange (Wellesley College) as part of Computability theory and applica
tions\n\n\nAbstract\nIn earlier work with Knight and Solomon\, we bounded
the computational complexity of the root-taking process over Puiseux and H
ahn series\, two kinds of generalized power series. But it is open whether
the bounds given are optimal. By looking at the most basic steps in the r
oot-taking process for Hahn series\, we together with Hall and Knight beca
me interested in the complexity of problems associated with well-ordered s
ubsets of a fixed ordered abelian group. Here we provide an overview of th
e results so far in both these settings.\n
LOCATION:https://researchseminars.org/talk/CTA/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Linda Brown Westrick (Penn State)
DTSTART;VALUE=DATE-TIME:20201208T210000Z
DTEND;VALUE=DATE-TIME:20201208T220000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/29
DESCRIPTION:Title: Luz
in's (N) and randomness reflection\nby Linda Brown Westrick (Penn Stat
e) as part of Computability theory and applications\n\n\nAbstract\nWe show
that a computable real-valued function f has Luzin's property (N) if and
only if it reflects Pi^1_1-randomness\, if and only if it reflects Delta^1
_1-randomness relative to Kleene's O\, and if and only if it reflects Kurt
z randomness relative to Kleene's O. Here a function f is said to reflect
a randomness notion R if whenever f(x) is R-random\, then x is R-random a
s well. If additionally f is known to have bounded variation\, then we sho
w f has Luzin's (N) if and only if it reflects weak-2-randomness\, and if
and only if it reflects Kurtz randomness relative to 0'. This links class
ical real analysis with algorithmic randomness. Joint with Arno Pauly and
Liang Yu.\n
LOCATION:https://researchseminars.org/talk/CTA/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Timothy McNicholl (Iowa State University)
DTSTART;VALUE=DATE-TIME:20200923T000000Z
DTEND;VALUE=DATE-TIME:20200923T010000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/30
DESCRIPTION:Title: Whi
ch Lebesgue spaces are computably presentable?\nby Timothy McNicholl (
Iowa State University) as part of Computability theory and applications\n\
n\nAbstract\nWe consider the following question: ``If there is a computabl
y presentable $L^p$ space\, does it follow that $p$ is computable?” The
answer is of course `no’ since the 1-dimensional $L^p$ space is just th
e field of scalars. So\, we turn to non-trivial cases. Namely\, assume t
here is a computably presentable $L^p$ space whose dimension is at least $
2$. We prove $p$ is computable if the space is finite-dimensional or if $
p \\geq 2$. We then show that if $1 \\leq p < 2$\, and if $L^p[0\,1]$ is
computably presentable\, then $p$ is right-c.e.. Finally\, we show there
is no uniform solution of this problem even when given upper and lower bou
nds on the exponent. The proof of this result leads to some basic results
on the effective theory of stable random variables. Finally\, we conject
ure that the answer to this question is `no’ and that right-c.e.-ness of
the exponent is the best result possible.\n
LOCATION:https://researchseminars.org/talk/CTA/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Paul-Elliot Angles d'Auriac (University of Lyon)
DTSTART;VALUE=DATE-TIME:20201006T130000Z
DTEND;VALUE=DATE-TIME:20201006T140000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/31
DESCRIPTION:Title: The
computable strength of Milliken's Tree Theorem and applications\nby P
aul-Elliot Angles d'Auriac (University of Lyon) as part of Computability t
heory and applications\n\n\nAbstract\nDevlin's theorem and the Rado graph
theorem are both variants of Ramsey's theorem\, where a structure is added
but more colors are allowed: Devlin's theorem (respectively the Rado grap
h theorem) states if S is ℚ (respectively G\, the Rado graph)\, then for
any size of tuple n\, there exists a number of colors l such that for any
coloring of [S]^n into finitely many colors\, there exists a subcopy of S
on which the coloring takes at most l colors. Moreover\, given n\, the op
timal l is specified.\n\nThe key combinatorial theorem used in both the pr
oof of Devlin's theorem and the Rado graph theorem is Milliken's tree theo
rem. Milliken's tree theorem is also a variant of Ramsey's theorem\, but t
his time for trees and strong subtrees: it states that given a coloring of
the strong subtrees of height n of a tree T\, there exists a strong subtr
ee of height ω of T on which the coloring is constant.\n\nIn this talk\,
we review the links between those theorems\, and present the recent result
s on the computable strength of Milliken's tree theorem and its applicatio
ns Devlin and the Rado graph theorem\, obtained with Cholak\, Dzhafarov\,
Monin and Patey.\n
LOCATION:https://researchseminars.org/talk/CTA/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexandra Soskova (Sofia University)
DTSTART;VALUE=DATE-TIME:20201020T140000Z
DTEND;VALUE=DATE-TIME:20201020T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/32
DESCRIPTION:Title: Eff
ective embeddings and interpretations\nby Alexandra Soskova (Sofia Uni
versity) as part of Computability theory and applications\n\n\nAbstract\nF
riedman and Stanley introduced Borel embeddings as a way of comparing clas
sification problems for different classes of structures. Many Borel embe
ddings are actually Turing computable. The effective decoding is given by
a uniform effective interpretation. Part of the effective interpretation
is actually Medvedev reduction. \nThe class of undirected graphs and the
class of linear orderings both lie on top under Turing computable embeddin
gs. We give examples of graphs that are not Medvedev reducible to any lin
ear ordering\, or to the jump of any linear ordering. For any graph\, the
re is a linear ordering\, that the graph is Medvedev reducible to the seco
nd jump of the linear ordering. Friedman and Stanley gave a Turing comput
able embedding $L$ of directed graphs in linear orderings. We show that t
here do not exist $L_{\\omega_1\\omega}$-formulas that uniformly interpret
the input graph $G$ in the output linear ordering $L(G)$. This is joint w
ork with Knight\, and Vatev.\n\nWe have also one positive result --- we pr
ove that the class of fields is uniformly effectively interpreted without
parameters in the class of Heisenberg groups.\nThe second part is joint w
ork with Alvir\, Calvert\, Goodman\, Harizanov\, Knight\, Miller\, Moroz
ov\, and Weisshaar.\n
LOCATION:https://researchseminars.org/talk/CTA/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chris Conidis (CUNY-College of Staten Island)
DTSTART;VALUE=DATE-TIME:20201014T010000Z
DTEND;VALUE=DATE-TIME:20201014T020000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/33
DESCRIPTION:Title: Non
-arithmetic algebraic constructions\nby Chris Conidis (CUNY-College of
Staten Island) as part of Computability theory and applications\n\n\nAbst
ract\nWe examine two radical constructions\, one from ring theory and anot
her from module theory\, and produce a computable ring for each constructi
on where the corresponding radical is $\\Pi^1_1$-complete.\n
LOCATION:https://researchseminars.org/talk/CTA/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Manlio Valenti (Università di Udine)
DTSTART;VALUE=DATE-TIME:20201103T140000Z
DTEND;VALUE=DATE-TIME:20201103T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/34
DESCRIPTION:Title: On
the descriptive complexity of Fourier dimension and Salem sets\nby Man
lio Valenti (Università di Udine) as part of Computability theory and app
lications\n\n\nAbstract\nIt is known that\, for Borel sets\, the Fourier d
imension is less than or equal to the Hausdorff dimension. The sets for wh
ich the two notions agree are called Salem sets.\n\nIn this talk\, we expl
ore the descriptive complexity of the family of closed Salem subsets of th
e Euclidean space. We also show how these results yield a characterization
of the Weihrauch degree of the maps computing the Hausdorff or the Fourie
r dimensions.\n
LOCATION:https://researchseminars.org/talk/CTA/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laurent Bienvenu (Université de Bordeaux)
DTSTART;VALUE=DATE-TIME:20201110T140000Z
DTEND;VALUE=DATE-TIME:20201110T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/35
DESCRIPTION:Title: The
interplay between randomness and genericity\nby Laurent Bienvenu (Uni
versité de Bordeaux) as part of Computability theory and applications\n\n
\nAbstract\nIn computability theory\, one often think of (Cohen)-genericit
y and algorithmic randomness as orthogonal notions: a truly random real wi
ll look very non-generic\, and a truly generic real will look very non-ran
dom. This orthogonality is best incarnated by the result of Nies\, Stephan
and Terwijn that any 2-random real and 2-generic real form a minimal pair
for Turing reducibility. On the other hand\, we know from the Kucera-Gacs
theorem that for any n there is a 1-random real which computes an n-gener
ic one\, but also (and more surprisingly)\, by a result of Kautz that ever
y 2-random real computes a 1-generic real. These last two results tell us
that the interplay between randomness and genericity is rather complex whe
n “randomness” is between 1-random and 2-random or “genericity” be
tween 1-generic and 2-generic. It is this gray area that we will discuss i
n this talk (based on the paper of the same title\, joint work with Chris
Porter).\n
LOCATION:https://researchseminars.org/talk/CTA/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bjørn Kjos-Hanssen (University of Hawaii at Manoa)
DTSTART;VALUE=DATE-TIME:20201117T230000Z
DTEND;VALUE=DATE-TIME:20201118T000000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/36
DESCRIPTION:Title: A f
amily of metrics connecting Jaccard distance to normalized information dis
tance\nby Bjørn Kjos-Hanssen (University of Hawaii at Manoa) as part
of Computability theory and applications\n\n\nAbstract\nDistance metrics a
re used in a wide variety of scientific contexts. In a 2001 paper in the j
ournal Bioinformatics\, M. Li\, Badger\, Chen\, Kwong\, and Kearney introd
uced an information-based sequence distance. It is analogous to the famous
Jaccard distance on finite sets. Soon thereafter\, M. Li\, Chen\, X. Li\,
Ma and Vitányi (2004) rejected that distance in favor of what they call
the normalized information distance (NID). Raff and Nicholas (2017) propos
ed a return to the Bioinformatics distance\, based on further application-
informed criteria.\n\nWe attempt to shed some light on this "dispute" by s
howing that the Jaccard distance and the NID analogue form the extreme poi
nts of the set of metrics within a family of semimetrics studied by Jimén
ez\, Becerra\, and Gelbukh (2013).\n\nThe NID is based on Kolmogorov compl
exity\, and Terwijn\, Torenvliet and Vitányi (2011) showed that it is nei
ther upper semicomputable nor lower semicomputable. Our result gives a 2-d
imensional family including the NID as an extreme point. It would be inter
esting to know if any of these functions are semicomputable.\n
LOCATION:https://researchseminars.org/talk/CTA/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Keita Yokoyama (Japan Advanced Institute of Science and Technology
)
DTSTART;VALUE=DATE-TIME:20201216T003000Z
DTEND;VALUE=DATE-TIME:20201216T013000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/37
DESCRIPTION:Title: Aut
omorphism argument and reverse mathematics\nby Keita Yokoyama (Japan A
dvanced Institute of Science and Technology) as part of Computability theo
ry and applications\n\n\nAbstract\nIn the study of models of Peano (or fir
st-order) arithmetic\, there are\nmany results on recursively saturated mo
dels and their automorphisms.\nHere\, we apply such an argument to models
of second-order arithmetic\nand see that any countable recursively saturat
ed model (M\,S) of WKL_0*\nis isomorphic to its countable coded omega-subm
odel if\nSigma_1-induction fails in (M\,S). From this result\, we see some
\ninteresting but weird properties of WKL_0* with the absence of\nSigma_1-
induction such as the collapse of analytic hierarchy. This\nargument can a
lso be applied to the reverse mathematical study of\nRamsey's theorem for
pairs (RT22)\, and we see some new relations\nbetween the computability-th
eoretic characterizations of RT22 and the\nfamous open question on the fir
st-order part of RT22+RCA_0.\nThis work is a part of a larger project join
t with Marta Fiori\nCarones\, Leszek Kolodziejczyk\, Katarzyna Kowalik and
Tin Lok Wong.\n
LOCATION:https://researchseminars.org/talk/CTA/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Emanuele Frittaion (TU Darmstadt)
DTSTART;VALUE=DATE-TIME:20210119T090000Z
DTEND;VALUE=DATE-TIME:20210119T100000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/38
DESCRIPTION:Title: Gen
eric realizability for intuitionistic set theory\nby Emanuele Frittaio
n (TU Darmstadt) as part of Computability theory and applications\n\n\nAbs
tract\nGeneric realizability goes back to Kreisel's and Troelstra's interp
retation of intuitionistic second order arithmetic. It was later adapted t
o systems of intuitionistic set theory by Friedman\, Beeson\, McCarthy\, a
nd Rathjen. We survey known applications and present some recent ones. Joi
nt with Michael Rathjen and Takako Nemoto.\n
LOCATION:https://researchseminars.org/talk/CTA/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Giovanni Soldà (University of Leeds)
DTSTART;VALUE=DATE-TIME:20210126T150000Z
DTEND;VALUE=DATE-TIME:20210126T160000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/39
DESCRIPTION:Title: Riv
al-Sands principles in the Weihrauch degrees\nby Giovanni Soldà (Univ
ersity of Leeds) as part of Computability theory and applications\n\n\nAbs
tract\nwRSg and wRSgr are consequences of RSg\, a theorem about graphs pro
ved in 1980 by Rival and Sands. wRSg and wRSgr can be shown to be equivale
nt to Ramsey theorem for pairs over RCA_0\, but are computationally strict
ly weaker. In this talk\, we will study the Weihrauch degrees associated t
o these principles\, by comparing them with the degrees of other classical
theorems introduced in the analysis of RT22. This is a joint work with Ma
rta Fiori Carones and Paul Shafer.\n
LOCATION:https://researchseminars.org/talk/CTA/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Verónica Becher (Universidad de Buenos Aires)
DTSTART;VALUE=DATE-TIME:20210309T170000Z
DTEND;VALUE=DATE-TIME:20210309T180000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/40
DESCRIPTION:Title: Ope
n questions on randomness and uniform distribution\nby Verónica Bech
er (Universidad de Buenos Aires) as part of Computability theory and appli
cations\n\n\nAbstract\nHow is Martin-Löf randomness for real numbers rel
ated to the classical theory of uniform distribution? In this talk I revi
ew several results on this relation and I present several open questions.
\n
LOCATION:https://researchseminars.org/talk/CTA/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Victor Selivanov (Institute of Informatics Systems\, Novosibirsk)
DTSTART;VALUE=DATE-TIME:20210209T130000Z
DTEND;VALUE=DATE-TIME:20210209T140000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/41
DESCRIPTION:Title: Pri
mitive recursive ordered fields and some applications\nby Victor Seliv
anov (Institute of Informatics Systems\, Novosibirsk) as part of Computabi
lity theory and applications\n\n\nAbstract\nWe establish primitive recursi
ve versions of some known facts about computable ordered fields of reals a
nd the field of computable reals and then apply them to some problems in l
inear algebra and analysis. In particular\, we find a partial primitive re
cursive analog of Ershov-Madison’s theorem about real closures of comput
able ordered fields\, relate the corresponding fields to the primitive rec
ursive reals\, give sufficient conditions for primitive recursive root-fin
ding\, computing normal forms of matrices\, and computing solution operato
rs of some linear systems of PDE.\nThis is joint work with Svetlana Seliva
nova.\n
LOCATION:https://researchseminars.org/talk/CTA/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Arno Pauly (Swansea University)
DTSTART;VALUE=DATE-TIME:20210201T213000Z
DTEND;VALUE=DATE-TIME:20210201T223000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/42
DESCRIPTION:Title: The
structure of Weihrauch degrees - what we know and what we don't know\
nby Arno Pauly (Swansea University) as part of Computability theory and ap
plications\n\n\nAbstract\nThe Weihrauch degrees are a popular setting for
classifying the computational content of mathematical theorems. Understand
ing their structure is useful as technical tool in concrete classification
s. Moreover\, their structure tells us something about how degrees of non-
computability look like in principle. In this talk\, I'll summarize what i
s already known about the structure of the Weihrauch degrees\, and try to
draw attention to some open problems. For example. we know that they form
a distributive lattice\, which is not a Heyting algebra and which is not c
omplete. We have further natural algebraic operations\, and we know of a f
ew that they are definable in terms of others. The Medvedev degrees embed
into the Weihrauch degrees as a lattice\, as do the many-one degrees (but
in a weird way).\n
LOCATION:https://researchseminars.org/talk/CTA/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Verónica Becher (Universidad de Buenos Aires)
DTSTART;VALUE=DATE-TIME:20210215T213000Z
DTEND;VALUE=DATE-TIME:20210215T223000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/43
DESCRIPTION:Title: Nor
mal numbers and perfect necklaces\nby Verónica Becher (Universidad de
Buenos Aires) as part of Computability theory and applications\n\n\nAbstr
act\nThe most famous example of a normal number is Champernowne's constant
0.123456789101112… Although the definition is very simple\, the origina
l proof of normality requires quite some work. In this talk I present "per
fect necklaces"\, a combinatorial object that yields a simple proof of Cha
mpernowne's normality result. And with a class of them\, the "nested perfe
ct necklaces"\, I explain M. Levin's constant\, the number with the fastes
t known speed of convergence to normality.\n
LOCATION:https://researchseminars.org/talk/CTA/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kirsten Eisenträger (The Pennsylvania State University)
DTSTART;VALUE=DATE-TIME:20210301T213000Z
DTEND;VALUE=DATE-TIME:20210301T223000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/44
DESCRIPTION:Title: A t
opological approach to undefinability in algebraic extensions of the ratio
nals\nby Kirsten Eisenträger (The Pennsylvania State University) as p
art of Computability theory and applications\n\n\nAbstract\nIn 1970 Matiya
sevich proved that Hilbert’s Tenth Problem over the\nintegers is undecid
able\, building on work by Davis-Putnam-Robinson. Hilbert’s\nTenth Probl
em over the rationals is still open\, but it could be resolved by\ngiving
an existential definition of the integers inside the rationals. Proving\nw
hether such a definition exists is still out of reach. However\, we will s
how\nthat only “very few” algebraic extensions of the rationals have t
he property\nthat their ring of integers are existentially or universally
definable.\nEquipping the set of all algebraic extensions of the rationals
with a natural\ntopology\, we show that only a meager subset has this pro
perty. An important tool\nis a new normal form theorem for existential def
initions in such extensions. As\na corollary\, we construct countably many
distinct computable algebraic\nextensions whose rings of integers are nei
ther existentially nor universally\ndefinable. Joint work with Russell Mil
ler\, Caleb Springer\, and Linda Westrick.\n
LOCATION:https://researchseminars.org/talk/CTA/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chris Conidis (CUNY College of Staten Islan)
DTSTART;VALUE=DATE-TIME:20210315T203000Z
DTEND;VALUE=DATE-TIME:20210315T213000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/45
DESCRIPTION:Title: The
Reverse Mathematics of Noether's Decomposition Lemma\nby Chris Conidi
s (CUNY College of Staten Islan) as part of Computability theory and appli
cations\n\n\nAbstract\nWe will survey some recent results in the Reverse M
athematics of Noetherian Algebra\, and in particular Noether's Decompositi
on Lemma which states that a Noetherian ring has only finitely many minima
l prime ideals. Such an analysis naturally leads one to formulate a combin
atorial principle\, namely the Tree-Antichain Principle\, which states tha
t every binary-branching tree with infinitely many splittings has an infin
ite antichain.\n
LOCATION:https://researchseminars.org/talk/CTA/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julia Knight (University of Notre Dame)
DTSTART;VALUE=DATE-TIME:20210405T203000Z
DTEND;VALUE=DATE-TIME:20210405T213000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/46
DESCRIPTION:Title: Des
cribing structures and classes of structures\nby Julia Knight (Univers
ity of Notre Dame) as part of Computability theory and applications\n\n\nA
bstract\nThe talk will recall some definitions and results on Scott comple
xity of individual countable structures\, Borel complexity of classes of s
tructures\, and Borel cardinality\, for comparing classification problems
for different classes. I will try to indicate how methods from computabili
ty may sometimes be used in this connection\, even for results that do not
mention computability. I will state some results on torsion-free Abelian
groups\, due to Downey-Montalbán\, Hjorth\, Thomas\, and Paolini-Shelah.
Finally\, I will mention a project with Turbo Ho and Russell Miller\, sayi
ng what we would like to do\, but have not done.\n
LOCATION:https://researchseminars.org/talk/CTA/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noam Greenberg (Victoria University of Wellington)
DTSTART;VALUE=DATE-TIME:20210419T203000Z
DTEND;VALUE=DATE-TIME:20210419T213000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/47
DESCRIPTION:Title: The
strength of Borel Wadge comparability\nby Noam Greenberg (Victoria Un
iversity of Wellington) as part of Computability theory and applications\n
\n\nAbstract\nWadge’s comparability lemma says that the Borel sets are a
lmost linearly ordered under Wadge reducibility: for any two Borel sets A
and B\, either A is a continuous pre-image of B\, or B is a continuous pre
-image of the complement of A. Wadge’s proof uses Borel determinacy\, wh
ich is not provable in second order arithmetic (H. Friedman). Using deep a
nd complex techniques\, Louveau and Saint-Raymond showed that Borel Wadge
comparability is provable in second order arithmetic\, but did not explore
its precise proof-theoretic strength. I will discuss recent work aiming t
o clarify this.\n\nOne of the main technical tools we use is Montalbán’
s “true stage” machinery\, originally developed for iterated priority
constructions in computable structure theory\, but more recently used by D
ay and Marks for their resolution of the decomposability conjecture.\n\nJo
int work with Adam Day\, Matthew Harrison-Trainor\, and Dan Turetsky.\n
LOCATION:https://researchseminars.org/talk/CTA/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andre Nies (Auckland University)
DTSTART;VALUE=DATE-TIME:20210503T203000Z
DTEND;VALUE=DATE-TIME:20210503T213000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/48
DESCRIPTION:Title: Max
imal towers and ultrafilter bases in computability theory\nby Andre Ni
es (Auckland University) as part of Computability theory and applications\
n\n\nAbstract\nThe tower number and ultrafilter numbers are cardinal chara
cteristics from set theory that are defined in terms of sets of natural nu
mbers with almost inclusion. The former is the least size of a maximal tow
er. The latter is the least size of a collection of infinite sets with upw
ard closure a non-principal ultrafilter. \n\nTheir analogs in computabilit
y theory will be defined in terms of collections of computable sets\, give
n as the columns of a single set. We study their complexity using Medvedev
reducibility. For instance\, we show that the ultrafilter number is Medve
dev equivalent to the problem of finding a function that dominates all com
putable functions\, that is\, highness. In contrast\, each nonlow set unif
ormly computes a maximal tower. \n\nJoint work with Steffen Lempp\, Joseph
Miller\, and Mariya Soskova\n
LOCATION:https://researchseminars.org/talk/CTA/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mathieu Hoyrup (LORIA)
DTSTART;VALUE=DATE-TIME:20210202T150000Z
DTEND;VALUE=DATE-TIME:20210202T160000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/49
DESCRIPTION:Title: The
fixed-point property for represented spaces\nby Mathieu Hoyrup (LORIA
) as part of Computability theory and applications\n\n\nAbstract\nErshov's
generalization of Kleene's recursion theorem is a fixed-point theorem for
computable multi-valued functions on numbered sets. We study its continuo
us version for continuous multi-valued functions on represented spaces. We
obtain results explaining why the fixed-point theorem usually holds unifo
rmly and why in most cases it can only be proved by the diagonal argument.
We investigate restricted classes of spaces\, for which we give a complet
e characterization of the spaces with the fixed-point property: the counta
bly-based spaces and the spaces of open sets. We also give an application
to the base-complexity classification of topological spaces.\n
LOCATION:https://researchseminars.org/talk/CTA/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeff Hirst (Appalachian State University)
DTSTART;VALUE=DATE-TIME:20210223T200000Z
DTEND;VALUE=DATE-TIME:20210223T210000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/50
DESCRIPTION:Title: Cur
rent thoughts on Hindman’s Theorem\nby Jeff Hirst (Appalachian State
University) as part of Computability theory and applications\n\n\nAbstrac
t\nThe exact reverse mathematical strength of Hindman’s theorem is a lon
g standing open question. This talk will discuss efforts to carry out an
ultrafilter-based proof using only arithmetical comprehension. A particul
ar emphasis is the definability of a class of sets that witness that certa
in ultrafilters do not encode homogeneous sets for Hindman’s theorem.\n
LOCATION:https://researchseminars.org/talk/CTA/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luca San Mauro (Institute for Discrete Mathematics and Geometry)
DTSTART;VALUE=DATE-TIME:20210302T130000Z
DTEND;VALUE=DATE-TIME:20210302T140000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/51
DESCRIPTION:Title: Cla
ssifying word problems\nby Luca San Mauro (Institute for Discrete Math
ematics and Geometry) as part of Computability theory and applications\n\n
\nAbstract\nThe study of word problems dates back to the work of Dehn in \
n1911. Given a recursively presented algebra A\, the word problem of A is
\nto decide if two words in the generators of A refer to the same element.
\nNowadays\, much is known about the complexity of word problems for \nal
gebraic structures: e.g.\, the Novikov-Boone theorem – one of the most \
nspectacular applications of computability to general mathematics – \nst
ates that the word problem for finitely presented groups is \nunsolvable.
Yet\, the computability theoretic tools commonly employed to \nmeasure the
complexity of word problems (e.g.\, Turing or m-reducibility) \nare defin
ed for sets\, while it is generally acknowledged that many \ncomputational
facets of word problems emerge only if one interprets them \nas equivalen
ce relations.\nIn this work\, we revisit the world of word problems throug
h the lens of \nthe theory of equivalence relations\, which has grown imme
nsely in recent \ndecades. To do so\, we employ computable reducibility\,
a natural \neffectivization of Borel reducibility.\nThis is joint work wit
h Valentino Delle Rose and Andrea Sorbi.\n
LOCATION:https://researchseminars.org/talk/CTA/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Steffen Lempp (University of Wisconsin-Madison)
DTSTART;VALUE=DATE-TIME:20210331T010000Z
DTEND;VALUE=DATE-TIME:20210331T020000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/52
DESCRIPTION:Title: Dec
idability and Undecidability in the Enumeration Degrees\nby Steffen Le
mpp (University of Wisconsin-Madison) as part of Computability theory and
applications\n\n\nAbstract\nFor most “natural” degree structures\, the
full first-order theory (in the language of partial ordering) is as compl
icated full first or second-order arithmetic\, so it is natural to try to
determine the quantifier level at which undecidability starts. For most
“natural” degree structures\, this seems to happen when we move from t
he AE-theory to the EAE-theory.\nI will survey some of the results from th
e past fifty years in this area and then focus on a new joint result with
Slaman and M. Soskova on the degree structure of the enumeration degrees:
By proving a strong embedding result for finite distributive lattices into
intervals of the enumeration degrees\, we obtain the undecidability of th
e EAE-theory\, and a partial decidability result for the AE-theory\, namel
y\, for the extension of embeddings problem.\n
LOCATION:https://researchseminars.org/talk/CTA/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Iskander Kalimullin (Kazan (Volga Region) Federal University)
DTSTART;VALUE=DATE-TIME:20210323T140000Z
DTEND;VALUE=DATE-TIME:20210323T150000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/53
DESCRIPTION:Title: Pun
ctual categoricity and degrees of punctual categoricity for finitely gener
ated structures.\nby Iskander Kalimullin (Kazan (Volga Region) Federal
University) as part of Computability theory and applications\n\n\nAbstrac
t\nA punctual algebraic structure A (i.e.\, primitive recursive structure
on the universe $\\omega$) is punctually categorical if for every its punc
tual copy B there is an isomorphism from A onto B which is primitive recur
sive together with the inverse. We note that there is an unexpected dichot
omy for this notion: every punctually categorical structure is either fini
tely generated\, or locally finite. This dichotomy also holds for the stru
ctures which have a degree of punctual categoricity. For the finitely gene
rated structures we can describe the possible degrees of punctual categori
city. We have some partial results relating degrees of punctual categorici
ty of locally finite structures. The results obtained jointly with Alexand
er Melnikov.\n
LOCATION:https://researchseminars.org/talk/CTA/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Merlin Carl (Europa-Universität Flensburg)
DTSTART;VALUE=DATE-TIME:20210406T080000Z
DTEND;VALUE=DATE-TIME:20210406T093000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/54
DESCRIPTION:Title: Com
plexity and Decision Times for ITTMs - The Story of the Bold Conjecture\nby Merlin Carl (Europa-Universität Flensburg) as part of Computability
theory and applications\n\n\nAbstract\nInfinite Time Turing Machines (ITT
Ms)\, defined in the classical paper by Hamkins and Lewis\, allow Turing m
achines to run for transfinite ordinal time. One can then generalize notio
ns of time (Schindler) and space (Löwe) complexity to this setting. Löwe
's "bold conjecture" was whether the two notions are non-trivially connect
ed\, i.e.\, whether low space complexity implies low time complexity. In o
ur talk\, we will show that this conjecture fails. Showing this will\, how
ever\, leads naturally to a systematics study of decision and semi-decisio
n times on ITTMs\, which was done in joint work with Philipp Schlicht and
Philip Welch and led to connections with descriptive set theory and genera
lizations to the theory of ranks.\n\nJoint work with Philipp Schlicht and
Philip Welch.\n
LOCATION:https://researchseminars.org/talk/CTA/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Belanger (National University of Singapore)
DTSTART;VALUE=DATE-TIME:20210413T080000Z
DTEND;VALUE=DATE-TIME:20210413T090000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/55
DESCRIPTION:Title: Max
imal order types of well partial orders\nby David Belanger (National U
niversity of Singapore) as part of Computability theory and applications\n
\n\nAbstract\nWe outline a general approach for computing (bounds on) maxi
mal order types of certain well partial orders. This is part of an ongoing
project to generalize and extend work of van der Meeren characterising th
e Bachmann-Howard ordinal as such an order type. Joint with Andreas Weierm
ann.\n
LOCATION:https://researchseminars.org/talk/CTA/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vasco Brattka (Universität der Bundeswehr München)
DTSTART;VALUE=DATE-TIME:20210420T160000Z
DTEND;VALUE=DATE-TIME:20210420T173000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/56
DESCRIPTION:Title: The
Discontinuity Problem\nby Vasco Brattka (Universität der Bundeswehr
München) as part of Computability theory and applications\n\n\nAbstract\n
We introduce the discontinuity problem and we prove that under the axiom o
f determinacy it is actually the weakest discontinuous problem in the topo
logical Weihrauch lattice. We also discuss algebraic properties of the dis
continuity problem\, such as the fact that it parallelizes to the non-comp
utability problem. We also introduce an operation that we call stashing an
d show that is dual to parallelization. We show that the discontinuity pro
blem is the stashing of LLPO and several variants of it.\n
LOCATION:https://researchseminars.org/talk/CTA/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Liang Yu (Nanjing University)
DTSTART;VALUE=DATE-TIME:20210603T010000Z
DTEND;VALUE=DATE-TIME:20210603T023000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/57
DESCRIPTION:Title: Som
e consequences of TD and sTD.\nby Liang Yu (Nanjing University) as par
t of Computability theory and applications\n\n\nAbstract\nTD says that for
every cofinal set $A$ of \\emph{Turing degrees}\, $A$ contains an upper c
one\; and sTD says that for every set $A$ of \\emph{reals} with cofinal ra
nge in the Turing degrees\, $A$ has a pointed subset (a pointed set is a p
erfect set in which every real computes a representation of the set). We p
rove some consequences of TD and sTD. For example\, we prove that sTD impl
ies for every set of reals\, its Hausdorff dimension can be approximated b
y it closed subsets.\n
LOCATION:https://researchseminars.org/talk/CTA/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pavel Semukhin (University of Oxford)
DTSTART;VALUE=DATE-TIME:20210608T130000Z
DTEND;VALUE=DATE-TIME:20210608T140000Z
DTSTAMP;VALUE=DATE-TIME:20210804T233706Z
UID:CTA/58
DESCRIPTION:Title: The
Membership Problem for 2x2 integer matrices\nby Pavel Semukhin (Unive
rsity of Oxford) as part of Computability theory and applications\n\n\nAbs
tract\nThe Membership Problem for matrix semigroups is stated as follows:
given a finite collection of square matrices F = { M_1\,...\,M_k } and a t
arget matrix M\, decide if M can be presented as a product of matrices fro
m F. In other words\, decide if M belongs to the semigroup generated b
y F. It has been known for a long time that the Membership Problem is unde
cidable for 3x3 matrices. On the other hand\, it is a big open question wh
ether this problem is decidable for 2x2 matrices or for some special cases
of 3x3 matrices.\n\nIn our recent work\, we showed that the Membership Pr
oblem is decidable for 2x2 nonsingular integer matrices. In this talk\, I
will present a proof of this result which is based on a combination of dif
ferent ideas from linear algebra\, group theory\, and automata theory.\n
LOCATION:https://researchseminars.org/talk/CTA/58/
END:VEVENT
END:VCALENDAR