BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Theodore Slaman (UC Berkeley)
DTSTART:20200421T140000Z
DTEND:20200421T150000Z
DTSTAMP:20260314T091030Z
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:20200428T120000Z
DTEND:20200428T130000Z
DTSTAMP:20260314T091030Z
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:20200505T200000Z
DTEND:20200505T210000Z
DTSTAMP:20260314T091030Z
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:20200519T200000Z
DTEND:20200519T210000Z
DTSTAMP:20260314T091030Z
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:20200513T010000Z
DTEND:20200513T020000Z
DTSTAMP:20260314T091030Z
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:20200527T010000Z
DTEND:20200527T020000Z
DTSTAMP:20260314T091030Z
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:20200602T140000Z
DTEND:20200602T150000Z
DTSTAMP:20260314T091030Z
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:20200609T140000Z
DTEND:20200609T150000Z
DTSTAMP:20260314T091030Z
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:20200617T010000Z
DTEND:20200617T020000Z
DTSTAMP:20260314T091030Z
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:20200623T200000Z
DTEND:20200623T210000Z
DTSTAMP:20260314T091030Z
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:20200708T010000Z
DTEND:20200708T020000Z
DTSTAMP:20260314T091030Z
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:20200714T200000Z
DTEND:20200714T210000Z
DTSTAMP:20260314T091030Z
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:20200630T140000Z
DTEND:20200630T150000Z
DTSTAMP:20260314T091030Z
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:20200721T150000Z
DTEND:20200721T160000Z
DTSTAMP:20260314T091030Z
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:20200728T210000Z
DTEND:20200728T220000Z
DTSTAMP:20260314T091030Z
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:20200804T140000Z
DTEND:20200804T150000Z
DTSTAMP:20260314T091030Z
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:20200811T140000Z
DTEND:20200811T150000Z
DTSTAMP:20260314T091030Z
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:20200818T200000Z
DTEND:20200818T210000Z
DTSTAMP:20260314T091030Z
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:20200826T010000Z
DTEND:20200826T020000Z
DTSTAMP:20260314T091030Z
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:20200901T200000Z
DTEND:20200901T210000Z
DTSTAMP:20260314T091030Z
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:20200908T140000Z
DTEND:20200908T150000Z
DTSTAMP:20260314T091030Z
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:20200915T130000Z
DTEND:20200915T140000Z
DTSTAMP:20260314T091030Z
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:20200915T200000Z
DTEND:20200915T210000Z
DTSTAMP:20260314T091030Z
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:20200929T200000Z
DTEND:20200929T210000Z
DTSTAMP:20260314T091030Z
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:20201013T200000Z
DTEND:20201013T210000Z
DTSTAMP:20260314T091030Z
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:20201027T200000Z
DTEND:20201027T210000Z
DTSTAMP:20260314T091030Z
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:20201110T210000Z
DTEND:20201110T220000Z
DTSTAMP:20260314T091030Z
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:20201124T210000Z
DTEND:20201124T220000Z
DTSTAMP:20260314T091030Z
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:20201208T210000Z
DTEND:20201208T220000Z
DTSTAMP:20260314T091030Z
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:20200923T000000Z
DTEND:20200923T010000Z
DTSTAMP:20260314T091030Z
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:20201006T130000Z
DTEND:20201006T140000Z
DTSTAMP:20260314T091030Z
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:20201020T140000Z
DTEND:20201020T150000Z
DTSTAMP:20260314T091030Z
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:20201014T010000Z
DTEND:20201014T020000Z
DTSTAMP:20260314T091030Z
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:20201103T140000Z
DTEND:20201103T150000Z
DTSTAMP:20260314T091030Z
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:20201110T140000Z
DTEND:20201110T150000Z
DTSTAMP:20260314T091030Z
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:20201117T230000Z
DTEND:20201118T000000Z
DTSTAMP:20260314T091030Z
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:20201216T003000Z
DTEND:20201216T013000Z
DTSTAMP:20260314T091030Z
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:20210119T090000Z
DTEND:20210119T100000Z
DTSTAMP:20260314T091030Z
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:20210126T150000Z
DTEND:20210126T160000Z
DTSTAMP:20260314T091030Z
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:20210309T170000Z
DTEND:20210309T180000Z
DTSTAMP:20260314T091030Z
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:20210209T130000Z
DTEND:20210209T140000Z
DTSTAMP:20260314T091030Z
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:20210201T213000Z
DTEND:20210201T223000Z
DTSTAMP:20260314T091030Z
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:20210215T213000Z
DTEND:20210215T223000Z
DTSTAMP:20260314T091030Z
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:20210301T213000Z
DTEND:20210301T223000Z
DTSTAMP:20260314T091030Z
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:20210315T203000Z
DTEND:20210315T213000Z
DTSTAMP:20260314T091030Z
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:20210405T203000Z
DTEND:20210405T213000Z
DTSTAMP:20260314T091030Z
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:20210419T203000Z
DTEND:20210419T213000Z
DTSTAMP:20260314T091030Z
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:20210503T203000Z
DTEND:20210503T213000Z
DTSTAMP:20260314T091030Z
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:20210202T150000Z
DTEND:20210202T160000Z
DTSTAMP:20260314T091030Z
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:20210223T200000Z
DTEND:20210223T210000Z
DTSTAMP:20260314T091030Z
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:20210302T130000Z
DTEND:20210302T140000Z
DTSTAMP:20260314T091030Z
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:20210331T010000Z
DTEND:20210331T020000Z
DTSTAMP:20260314T091030Z
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:20210323T140000Z
DTEND:20210323T150000Z
DTSTAMP:20260314T091030Z
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:20210406T080000Z
DTEND:20210406T093000Z
DTSTAMP:20260314T091030Z
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:20210413T080000Z
DTEND:20210413T090000Z
DTSTAMP:20260314T091030Z
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:20210420T160000Z
DTEND:20210420T173000Z
DTSTAMP:20260314T091030Z
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:20210603T010000Z
DTEND:20210603T023000Z
DTSTAMP:20260314T091030Z
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:20210608T130000Z
DTEND:20210608T140000Z
DTSTAMP:20260314T091030Z
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
BEGIN:VEVENT
SUMMARY:Rachael Alvir (University of Notre Dame)
DTSTART:20210913T203000Z
DTEND:20210913T210000Z
DTSTAMP:20260314T091030Z
UID:CTA/59
DESCRIPTION:Title: Fin
itely α-generated Structures\nby Rachael Alvir (University of Notre D
ame) as part of Computability theory and applications\n\n\nAbstract\nIn th
is talk\, we define the notion of a finitely α-generated structure and ge
neralize results about Scott sentences earlier known only for finitely gen
erated structures. We will show how these results can be used to the conne
ct some of the existing non-equivalent definitions of Scott rank.\n
LOCATION:https://researchseminars.org/talk/CTA/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josiah Jacobsen-Grocott (University of Wisconsin)
DTSTART:20210913T210000Z
DTEND:20210913T213000Z
DTSTAMP:20260314T091030Z
UID:CTA/60
DESCRIPTION:Title: A C
haracterization of the Strongly η-Representable Many-One Degrees\nby
Josiah Jacobsen-Grocott (University of Wisconsin) as part of Computability
theory and applications\n\n\nAbstract\nη-representations are a way of co
ding sets in computable linear orders that were first introduced by Fellne
r in his thesis. Limitwise monotonic functions have been used to character
ize the sets with η-representations and give characterizations for severa
l variations of η-representations. The one exception is the class of sets
with strong η-representations\, the only class where the order type of t
he representation is unique. We introduce the notion of a connected approx
imation of a set\, a variation on Σ02 approximations. We use connected ap
proximations to give a characterization of the many-one degrees of sets wi
th strong η-representations as well as new characterizations of the varia
tions of η-representations with known characterizations.\n
LOCATION:https://researchseminars.org/talk/CTA/60/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benoit Monin (Créteil University)
DTSTART:20210927T203000Z
DTEND:20210927T213000Z
DTSTAMP:20260314T091030Z
UID:CTA/61
DESCRIPTION:Title: The
computational content of Milliken’s tree theorem\nby Benoit Monin (
Créteil University) as part of Computability theory and applications\n\n\
nAbstract\nThe Milliken’s tree theorem is an extension of Ramsey’s the
orem to trees. It implies for instance that if we assign to all the sets o
f two strings of the same length\, one among k colors\, there is an infini
te binary tree within which every pair of strings of the same length has t
he same color. We are going to present some results on Milliken’s tree t
heorem from the viewpoint of computability theory and reverse mathematics.
\n
LOCATION:https://researchseminars.org/talk/CTA/61/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vittorio Cipriani (University of Udine)
DTSTART:20211011T203000Z
DTEND:20211011T210000Z
DTSTAMP:20260314T091030Z
UID:CTA/62
DESCRIPTION:Title: Can
tor-Bendixson Theorem in the Weihrauch lattice\nby Vittorio Cipriani (
University of Udine) as part of Computability theory and applications\n\n\
nAbstract\nIn this talk we will study the Cantor-Bendixson theorem using t
he\nframework of Weihrauch reducibility. (Variations of) this theorem fall
s into\nthe highest of the big-five axiom systems of reverse mathematics\,
namely\n\\Pi_1^1-CA_0 . Kihara\, Marcone and Pauly already showed that ma
ny problems\nrepresenting principles equivalent to ATR_0 lie in different
Weihrauch\ndegrees\, for \\Pi_1^1-CA_0 we actually have a natural candidat
e\, namely the one\nmapping a countable sequence of trees to the character
istic function of the\nset of indices corresponding to well-founded trees.
This principle was firstly\nconsidered by Hirst\, that also showed its We
ihrauch equivalence with PK_Tr\,\nthe function that takes as input a tree
and outputs its perfect kernel for\ntrees. Even if in reverse mathematics
it is actually equivalent to consider\ntrees or closed sets\, we will show
that PK_Tr <_W PK_X\, where PK_X takes as\ninput a closed set of a comput
able Polish space X and outputs its perfect\nkernel. The equivalence betwe
en these two shows up if we switch to\narithmetical Weihrauch reducibility
.\n\nWe will continue in this direction showing (non) reductions between p
roblems\nrelated to the Cantor-Bendixson theorem with particular attention
paid to\nclassify them for every computable Polish space X. This leads us
to the result\nthat\, while PK_X and wCB_X (i.e. same as PK_X but where t
he output also\nprovides a listing of the elements in the scattered part)
are equivalent for\nany space X that we consider\, the problem CB_X (i.e.
same as wCB_X but where\nthe output provides also the cardinality of the s
cattered part) "almost"\nsplits in two Weihrauch degrees\, one having as r
epresentative PK_X and the\nother having CB_\\Baire.\n\nThis is joint work
with Alberto Marcone and Manlio Valenti.\n
LOCATION:https://researchseminars.org/talk/CTA/62/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Webb (University of Hawaiʻi at Mānoa)
DTSTART:20211011T210000Z
DTEND:20211011T213000Z
DTSTAMP:20260314T091030Z
UID:CTA/63
DESCRIPTION:by David Webb (University of Hawaiʻi at Mānoa) as part of Co
mputability theory and applications\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/CTA/63/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sarah Reitzes (University of Chicago)
DTSTART:20211025T203000Z
DTEND:20211025T210000Z
DTSTAMP:20260314T091030Z
UID:CTA/64
DESCRIPTION:Title: Com
paring induction and bounding principles over RCA0 and RCA*0\nby Sarah
Reitzes (University of Chicago) as part of Computability theory and appli
cations\n\n\nAbstract\nIn this talk\, I will discuss joint work with Damir
D. Dzhafarov and Denis R. Hirschfeldt\, and more recent work following th
at line of research. Our work centers on the characterization of reduction
s between Π12 problems P and Q in terms of winning strategies in certain
games. These characterizations were originally introduced by Hirschfeldt a
nd Jockusch in [1]. I will discuss extensions and generalizations of these
characterizations\, including a certain notion of compactness that allows
us\, for strategies satisfying particular conditions\, to bound the numbe
r of moves it takes to win. This bound is independent of the instance of t
he problem P being considered. This allows us to develop the idea of Weihr
auch and generalized Weihrauch reduction over some base theory. Here\, we
will focus on the base theory RCA0 and the weaker system RCA*0. In this ta
lk\, I will explore these notions of reduction among various principles\,
including bounding and induction principles. I will present a metatheorem
that allows us to obtain many nonreductions between these principles. \n\n
[1] D. R. Hirschfeldt and C. G. Jockusch\, Jr.: On notions of computabilit
y-theoretic reduction between Π12 principles. Journal of Mathematical Log
ic 16 (1650002)\, 59 pp. (2016)\n
LOCATION:https://researchseminars.org/talk/CTA/64/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Diego Rojas (Iowa State University)
DTSTART:20211025T210000Z
DTEND:20211025T213000Z
DTSTAMP:20260314T091030Z
UID:CTA/65
DESCRIPTION:Title: Eff
ective convergence notions for measures on the real line\nby Diego Roj
as (Iowa State University) as part of Computability theory and application
s\n\n\nAbstract\nIn classical measure theory\, there are two primary conve
rgence notions studied for sequences of measures: weak and vague convergen
ce. In this talk\, we discuss a framework to study the effective theory of
weak and vague convergence of measures on the real line. For effective we
ak convergence\, we give an effective version of a characterization theore
m for weak convergence called the Portmanteau Theorem. We also discuss the
relationship between effective weak convergence and the structure of the
space of finite Borel measures on the real line as a computable metric spa
ce. In contrast to effective weak convergence\, we give an example of an e
ffectively vaguely convergent sequence of measures that has an incomputabl
e limit. Nevertheless\, we discuss the conditions for which the limit of a
n effectively vaguely convergent sequence is computable and the conditions
for which effective weak and vague convergence of measures coincide. This
talk will feature joint work with Timothy McNicholl.\n
LOCATION:https://researchseminars.org/talk/CTA/65/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cristóbal Rojas (Pontifical Catholic University of Chile)
DTSTART:20211108T213000Z
DTEND:20211108T223000Z
DTSTAMP:20260314T091030Z
UID:CTA/66
DESCRIPTION:Title: Com
putability of Harmonic Measure\nby Cristóbal Rojas (Pontifical Cathol
ic University of Chile) as part of Computability theory and applications\n
\n\nAbstract\nWe will review recent results relating the geometry of a con
nected domain to the computability of its harmonic measure at a given poin
t x. In particular\, we will discuss examples of domains whose harmonic me
asure at x is always computable relative to x\, but not uniformly. As a by
-product\, this construction produces "natural" examples of harmonic funct
ions arising as solutions to a Dirichlet problem which are piecewise compu
table (i.e. all their values are computable relative to the input point)\,
but not computable. This is a work in collaboration with I. Binder\, A. G
lucksam and M. Yampolsky.\n
LOCATION:https://researchseminars.org/talk/CTA/66/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Elvira Mayordomo (University of Zaragoza)
DTSTART:20211122T213000Z
DTEND:20211122T223000Z
DTSTAMP:20260314T091030Z
UID:CTA/67
DESCRIPTION:Title: Ext
ending the reach of the point-to-set principle\nby Elvira Mayordomo (U
niversity of Zaragoza) as part of Computability theory and applications\n\
n\nAbstract\nThe point-to-set principle of J. Lutz and N. Lutz (2018) has\
nrecently enabled the theory of computing to be used to answer open questi
ons\nabout fractal geometry in Euclidean spaces R^n. These are classical q
uestions\nwhose statements do not involve computation or related aspects o
f logic.\n\nI will present the generalization of the point-to-set principl
e from Euclidean\nspaces to arbitrary separable metric spaces and to a lar
ge class of gauge\nfamilies.\n\nThen I will demonstrate the power of our e
xtended point-to-set principle by\nusing it to prove new theorems about cl
assical fractal dimensions in\nhyperspaces.\n\n(The results presented are
joint work with Jack Lutz and Neil Lutz).\n
LOCATION:https://researchseminars.org/talk/CTA/67/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Francesca Zaffora Blando (Carnegie Mellon University)
DTSTART:20211206T213000Z
DTEND:20211206T223000Z
DTSTAMP:20260314T091030Z
UID:CTA/68
DESCRIPTION:Title: Alg
orithmic randomness and Bayesian convergence\nby Francesca Zaffora Bla
ndo (Carnegie Mellon University) as part of Computability theory and appli
cations\n\n\nAbstract\nMuch recent work in algorithmic randomness has conc
erned\ncharacterizations of randomness notions in terms of effectivization
s of\nalmost-everywhere convergence theorems in analysis and probability t
heory. In\nthis talk\, I will consider some results that are part of the b
asic toolkit of\nBayesian epistemologists from this perspective. In partic
ular\, I will focus on\ncertain martingale convergence theorems that form
one of the cornerstones of\nBayesian epistemology and that fall under the
general umbrella of "Bayesian\nconvergence-to-the-truth results". These re
sults are standardly taken to\nestablish that a Bayesian agent’s beliefs
are guaranteed to converge to the\ntruth with probability one as the evid
ence accumulates. We will see that\, for\ncomputable Bayesian agents (i.e.
\, Bayesian agents with computable priors)\, we\nnot only have that conver
gence to the truth occurs with probability one\, but\nwe can also provide
precise characterizations of the data streams along which\nbeliefs converg
e to the truth: they are precisely the algorithmically random\ndata stream
s. I will conclude by sketching a broader computability-theoretic\napproac
h to Bayesian epistemology suggested by these results.\n
LOCATION:https://researchseminars.org/talk/CTA/68/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Takayuki Kihara (Nagoya University)
DTSTART:20211005T130000Z
DTEND:20211005T140000Z
DTSTAMP:20260314T091030Z
UID:CTA/69
DESCRIPTION:Title: Law
vere-Tierney topologies for computability theorists\nby Takayuki Kihar
a (Nagoya University) as part of Computability theory and applications\n\n
\nAbstract\nIn this talk\, we study the frame of Lawvere-Tierney topologie
s on Hyland's effective topos. For this purpose\, we introduce a new compu
tability-theoretic reducibility notion\, which is a common extension of th
e notions of Turing reducibility and generalized Weihrauch reducibility. B
ased on the work by Lee and van Oosten\, we utilize this reducibility noti
on for providing a concrete description of the frame of the Lawvere-Tierne
y topologies on the effective topos. As an application\, we solve several
open problems proposed by Lee and van Oosten. For instance\, we show that
there exists no minimal Lawvere-Tierney topology which is strictly above t
he identity topology on the effective topos.\n
LOCATION:https://researchseminars.org/talk/CTA/69/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dino Rossegger (UC Berkeley)
DTSTART:20211102T200000Z
DTEND:20211102T210000Z
DTSTAMP:20260314T091030Z
UID:CTA/70
DESCRIPTION:Title: New
examples of degrees of categoricity\nby Dino Rossegger (UC Berkeley)
as part of Computability theory and applications\n\n\nAbstract\nWe confirm
a conjecture by Csima and Ng that if $\\mathbf d$ is a Turing degree with
$\\mathbf 0^{(\\alpha)}\\leq \\mathbf d\\leq \\mathbf 0^{(\\alpha+1)}$ fo
r some computable $\\alpha$\, then $\\mathbf d$ is a degree of categoricit
y. For $\\alpha\\geq 2$ we modify a technique developed by Dan Turetsky to
code paths through trees into the automorphisms of structures. This allow
s us to obtain structures with these degrees of categoricity that are rigi
d and have computable dimension $2$. For both properties\, this is the lea
st $\\alpha$ where we can obtain this result. Goncharov showed that if a s
tructure is $\\mathbf 0'$-computably categorical\, then it can not have fi
nite computable dimension other than $1$. Bazhenov and Yamaleev constructe
d a properly d-c.e.\\ degree $\\mathbf d$\, that is not the degree of cate
goricity of a rigid structure. We combine their construction with true sta
ges to obtain a degree $\\mathbf d$\, $\\mathbf 0'<\\mathbf d< \\mathbf 0'
'$ that is not the degree of categoricity of a rigid structure. This is jo
int work with Barbara Csima.\n
LOCATION:https://researchseminars.org/talk/CTA/70/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Karen Seidel (Hasso Plattner Institute\, University of Potsdam)
DTSTART:20211130T200000Z
DTEND:20211130T210000Z
DTSTAMP:20260314T091030Z
UID:CTA/71
DESCRIPTION:Title: Mod
elling binary classification\nby Karen Seidel (Hasso Plattner Institut
e\, University of Potsdam) as part of Computability theory and application
s\n\n\nAbstract\nIn machine learning\, algorithms generalise from availabl
e training data to unseen situations.\nThe engineering practices used in t
he respective technologies are far from understood.\nResearch in \\emph{in
ductive inference} analyses concrete mathematical models for this complex
subject with tools from computability theory.\n\nWe investigate models for
incremental binary classification\, an example for supervised online lear
ning.\nOur starting point is a model for human and machine learning sugges
ted by E.~M.~Gold.\n\nFor learning algorithms that use all of the availabl
e binary labeled training data in order to compute the current hypothesis\
, we observe that the distribution of the training data does not influence
learnability.\nWhen approximating the concept to be learned\, we obtain a
strict hierarchy\, depending on the error parameter.\nWe consider differe
nt hypothesis spaces for spam problem like and symmetric classification ta
sks and provide the complete maps.\n
LOCATION:https://researchseminars.org/talk/CTA/71/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Donald Stull (Northwestern University)
DTSTART:20220124T213000Z
DTEND:20220124T223000Z
DTSTAMP:20260314T091030Z
UID:CTA/72
DESCRIPTION:Title: The
dimension spectrum conjecture for lines\nby Donald Stull (Northwester
n University) as part of Computability theory and applications\n\n\nAbstra
ct\nEffective dimension gives a fine-grained measure of randomness of indi
vidual points in Euclidean space. Let L be a line in the Euclidean plane.
The dimension spectrum sp(L) is the set of all effective dimensions of ind
ividual points on L. Jack Lutz\, in the early 2000s\, posed the dimension
spectrum conjecture. This conjecture states that\, for every line L\, sp(L
) contains a unit interval. In this talk\, we present a proof of the dimen
sion spectrum conjecture. We also discuss its relation to open problems in
geometric measure theory\, and avenues for future research.\n
LOCATION:https://researchseminars.org/talk/CTA/72/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Harrison-Trainor (University of Michigan)
DTSTART:20220207T213000Z
DTEND:20220207T223000Z
DTSTAMP:20260314T091030Z
UID:CTA/73
DESCRIPTION:Title: Kol
mogorov extractors and evenly-distributed hypergraphs\nby Matthew Harr
ison-Trainor (University of Michigan) as part of Computability theory and
applications\n\n\nAbstract\nSuppose that we have a string which has some a
mount of randomness\nand we want to produce from it\, in an effective way\
, a string which is more\nrandom. Though we cannot do this\, it is possibl
e to produce two strings\, at\nleast one of which is more random than the
original string. Moreover\, the more\nstrings we are allowed to produce\,
the more we can increase the randomness.\nHow much can we increase the ran
domness\, and how many strings are required?\nThis question turns out to b
e related to a purely graph-theoretic question\nabout how evenly the edges
of a hypergraph can be distributed.\n
LOCATION:https://researchseminars.org/talk/CTA/73/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ekaterina Fokina (Vienna University of Technology)
DTSTART:20220221T213000Z
DTEND:20220221T223000Z
DTSTAMP:20260314T091030Z
UID:CTA/74
DESCRIPTION:Title: Alg
orithmic learning of structures\nby Ekaterina Fokina (Vienna Universit
y of Technology) as part of Computability theory and applications\n\n\nAbs
tract\nAssume we have a class of structures closed under isomorphism.\nAss
ume further\, we receive information about one of these structures step by
\nstep: finitely much information at each step. Our goal is to determine\,
after\nfinitely many steps\, which structure from the class we are observ
ing. If we\ncan reach the goal\, we call the class learnable. In the talk
we formalise\nvarious aspects of this problem using ideas from computable
structure theory\nand computational learning theory. We give syntactic cha
racterisations for\nseveral notions of learnability and apply these result
s to get examples of\nlearnable and non-learnable classes of structures.\n
LOCATION:https://researchseminars.org/talk/CTA/74/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Emmanuel Rauzy (Université de Paris)
DTSTART:20220201T160000Z
DTEND:20220201T170000Z
DTSTAMP:20260314T091030Z
UID:CTA/75
DESCRIPTION:Title: Com
putable analysis on the space of marked groups\nby Emmanuel Rauzy (Uni
versité de Paris) as part of Computability theory and applications\n\n\nA
bstract\nI will present some results that concern the study of Markovian c
omputable analysis on the topological space of marked groups. While this w
ork was originally motivated by questions in group theory\, it turned out
to be also very interesting from the point of view of computable analysis
alone\, providing the first naturally arising Polish space that is not eff
ectively Polish.\nIndeed\, while it is effectively complete and separable\
, the space of marked groups is not effectively separable: any sequence th
at is dense in it is non-computable. I will also present a phenomenon of f
ailure of an effective axiom of choice: there is no algorithm that can\, g
iven a non-empty basic clopen set\, produce a group that belongs to this s
et. Because of this\, none of the well known results of Kreisel-Lacombe-Sc
hoenfield\, Ceitin and Moschovakis\, and that establish the effective cont
inuity of computable functions in different settings\, can be applied to t
he space of marked groups.\nMy talk will focus on presenting some classica
l theorems of the theory of decision problems for groups (Boone-Novikov\,
Boone-Rogers\, etc)\, in order to show how those theorems apply to the spa
ce of marked groups.\n
LOCATION:https://researchseminars.org/talk/CTA/75/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yue Yang (National University of Singapore)
DTSTART:20220215T010000Z
DTEND:20220215T020000Z
DTSTAMP:20260314T091030Z
UID:CTA/76
DESCRIPTION:Title: Str
ong minimal pair problem\nby Yue Yang (National University of Singapor
e) as part of Computability theory and applications\n\n\nAbstract\nThis ta
lk is about recursively enumerable (r.e.) Turing degrees. We say that two
nonzero r.e. degrees a and b form a strong minimal pair\, if a ∧ b = 0 a
nd for any nonzero r.e. degree x ≤ a\, b ∨ x ≥ a. Joint with Mingzho
ng Cai\, Yiqun Liu\, Yong Liu\, and Cheng Peng\, we are able to show the n
onexistence of such a pair. I will not make any attempt to outline the pro
of. Instead\, I plan to talk about our result in relation to earlier ones
in the literature\, and mention a few interesting (or strange) features of
the construction. For instance\, the construction is highly nonuniform\,
we have to prepare three different (families of) sets and one of them will
win. Furthermore\, the index of the winning set can only be found using 0
^(4). I will also make some comments about the priority methods in general
and raise some questions hoping to hear suggestions from the audiences.\n
LOCATION:https://researchseminars.org/talk/CTA/76/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tin Lok Wong (National University of Singapore)
DTSTART:20211215T090000Z
DTEND:20211215T100000Z
DTSTAMP:20260314T091030Z
UID:CTA/77
DESCRIPTION:Title: Ari
thmetic under negated induction\nby Tin Lok Wong (National University
of Singapore) as part of Computability theory and applications\n\n\nAbstra
ct\nArithmetic generally does not admit any non-trivial quantifier elimina
tion. I will talk about one exception\, where the negation of an induction
axiom is included in the theory. Here the Weak Koenig Lemma from reverse
mathematics arises as a model completion.This work is joint with Marta Fio
ri-Carones (Novosibirsk)\, Leszek Aleksander Kolodziejczyk (Warsaw) and Ke
ita Yokoyama (Sendai).\n
LOCATION:https://researchseminars.org/talk/CTA/77/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew de Brecht (Kyoto University)
DTSTART:20220111T120000Z
DTEND:20220111T130000Z
DTSTAMP:20260314T091030Z
UID:CTA/79
DESCRIPTION:Title: The
category of quasi-Polish spaces as a represented space\nby Matthew de
Brecht (Kyoto University) as part of Computability theory and application
s\n\n\nAbstract\nQuasi-Polish spaces are a class of well-behaved countably
based spaces which include Polish spaces\, omega-continuous domains\, and
countably based spectral spaces. In this talk\, we will show how to const
ruct the category of quasi-Polish spaces as a represented space\, and demo
nstrate the computability of some standard category-theoretical constructi
ons such as products and equalizers. As an example of some less trivial co
nstructions\, we use domain theoretic techniques to verify the computabili
ty of various powerspace functors on the category of quasi-Polish spaces.
(This work was supported by JSPS KAKENHI Grant Number 18K11166).\n
LOCATION:https://researchseminars.org/talk/CTA/79/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Peter Cholak (University of Notre-Dame)
DTSTART:20220301T200000Z
DTEND:20220301T210000Z
DTSTAMP:20260314T091030Z
UID:CTA/80
DESCRIPTION:Title: Old
and new results on the computably enumerable sets\nby Peter Cholak (U
niversity of Notre-Dame) as part of Computability theory and applications\
n\n\nAbstract\nWe will survey a number of old results on the computably en
umerable sets and finish with a few new results. The computably enumerabl
e sets are interesting since anything which can happen computably happens
in computably enumerable sets.\n
LOCATION:https://researchseminars.org/talk/CTA/80/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rupert Hölzl (UniBw Munich)
DTSTART:20220316T130000Z
DTEND:20220316T140000Z
DTSTAMP:20260314T091030Z
UID:CTA/81
DESCRIPTION:Title: Ran
k and Randomness (Cancelled)\nby Rupert Hölzl (UniBw Munich) as part
of Computability theory and applications\n\n\nAbstract\nThis talk has been
cancelled and will be moved to a later date.\n\nWe show that for each com
putable ordinal $\\alpha>\;0$ it is possible to find in\neach Martin-Lö
f random $\\Delta^0_2$ degree a sequence $R$ of Cantor-Bendixson\nrank $\\
alpha$\, while ensuring that the sequences that inductively witness $R$'s\
nrank are all Martin-Löf random with respect to a single countably suppor
ted\nand computable measure. This is a strengthening for random degrees of
a recent\nresult of Downey\, Wu\, and Yang\, and can be understood as a r
andomized version\nof it. (Joint result with Christopher P. Porter.)\n
LOCATION:https://researchseminars.org/talk/CTA/81/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Valentina Harizanov (George Washington University)
DTSTART:20220330T000000Z
DTEND:20220330T010000Z
DTSTAMP:20260314T091030Z
UID:CTA/82
DESCRIPTION:Title: Com
putable isomorphism problem\nby Valentina Harizanov (George Washington
University) as part of Computability theory and applications\n\n\nAbstrac
t\nThese classes include arbitrary structures with at least one relation o
f arity at least $2$\, abelian $p$-groups\, linear orders\, Boolean algebr
as\, fields of a fixed characteristic\, nilpotent semigroups\, nilpotent g
roups\, and nilpotent rings. These classes have isomorphic computable stru
ctures that are not hyperarithmetically isomorphic. One of the methods we
use to establish $\\Sigma _{1}^{1}$-completeness of the isomorphism proble
m for $K$ is based on a uniform effective interpretation\nof computable st
ructures in a specific class into computable structures in $K$.\n
LOCATION:https://researchseminars.org/talk/CTA/82/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Meng Che "Turbo" Ho (California State University Northridge)
DTSTART:20220321T203000Z
DTEND:20220321T213000Z
DTSTAMP:20260314T091030Z
UID:CTA/83
DESCRIPTION:Title: Zer
o-one laws for finitely presented structures\nby Meng Che "Turbo" Ho (
California State University Northridge) as part of Computability theory an
d applications\n\n\nAbstract\nGromov proposed the notion of random groups
as a model to study the typical behavior of finitely presented groups. The
y share many properties of the free group\, and Knight conjectured that ra
ndom groups satisfy the zero-one law and have the same first-order theory
as the free group. In this joint work with Franklin and Knight\, we study
this zero-one law in other classes of structures. In particular\, we consi
der random presentations in algebraic varieties in the sense of universal
algebra. We will discuss some examples where the zero-one law holds and so
me other examples where the zero-one law fails. We also establish some gen
eral conditions for the zero-one law to hold (or fail).\n
LOCATION:https://researchseminars.org/talk/CTA/83/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jun Le Goh (University of Wisconsin)
DTSTART:20220404T203000Z
DTEND:20220404T213000Z
DTSTAMP:20260314T091030Z
UID:CTA/84
DESCRIPTION:Title: Ext
ensions of embeddings in the $\\Sigma^0_2$ enumeration degrees\nby Jun
Le Goh (University of Wisconsin) as part of Computability theory and appl
ications\n\n\nAbstract\nIn order to \nmeasure the \nalgorithmic content of
partial functions\, or the positive information \ncontent of subsets of t
he natural numbers\, one can use the notion of \nenumeration reducibility.
The associated degree structure\, known as the \nenumeration degrees (e-d
egrees)\, forms a superstructure of the Turing \ndegrees. We present ongoi
ng work with Steffen Lempp\, Keng Meng Ng and \nMariya Soskova on the alge
braic properties of a countable substructure of \nthe e-degrees\, namely t
he &Sigma\;02 e-degr
ees.\n
\n\nThe &Sigma\;02 \ne-degrees are analogous to the \ncomputably enumerable (c.e.)
\nTuring degrees but these structures are not elementarily equivalent as
\npartial orders. Indeed\, Ahmad showed that there are incomparable \n&Sig
ma\;02\ne-degrees a
and b such that if c < a\, then \nc <
b\, implying that a cannot \nbe expressed as the join of two de
grees below it. This stands in contrast \nto Sacks's splitting theorem for
the c.e. Turing degrees.\n
\n\nOne can view Ahmad's result as a tw
o-quantifier sentence in the language \nof partial orders which holds in t
he &Sigma\;02 \ne-de
grees. While it is easy \nto compute whether a given one-quantifier senten
ce is true in the \n&Sigma\;02 \ne-degrees (because all finite partial orders embed)\, the \ncor
responding task for two-quantifier sentences (which corresponds to an \nex
tension of embeddings problem) is not known to be algorithmically \ndecida
ble. Towards solving this problem\, we investigate the extent to \nwhich A
hmad's result can be generalized. For instance\, we show that it \ndoes no
t generalize to triples: For any incomparable \n&Sigma\;02 e-degrees \na\, b and <
i>c\, there is some x such that one of \nthe following holds: <
i>x is \nbelow a but not below b\, or x is below
b but \nnot below c.\n
\n\nWe shall also discuss spec
ulative generalizations of the above result\, and \nhow they may lead to a
n algorithm which decides a class of two-quantifier \nsentences in the &Si
gma\;02 e-degrees.\n
LOCATION:https://researchseminars.org/talk/CTA/84/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Melnikov (Victoria University of Wellington)
DTSTART:20220412T010000Z
DTEND:20220412T020000Z
DTSTAMP:20260314T091030Z
UID:CTA/85
DESCRIPTION:Title: Pri
mitive recursive mathematics\nby Alexander Melnikov (Victoria Universi
ty of Wellington) as part of Computability theory and applications\n\n\nAb
stract\nWe discuss the recently revived approach to computable\nmathematic
s via primitive recursion. This theory aims to\neliminate the use of unbou
nded search from \ncomputable structure theory\, computable analysis\, etc
.\nWe will be focused on the recent developments in the theory\,\nbut we b
egin with an overview of what is known so far.\n
LOCATION:https://researchseminars.org/talk/CTA/85/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeff Hirst (Appalachian State University)
DTSTART:20220418T203000Z
DTEND:20220418T213000Z
DTSTAMP:20260314T091030Z
UID:CTA/86
DESCRIPTION:Title: Thr
ee views of LPO and LLPO\nby Jeff Hirst (Appalachian State University)
as part of Computability theory and applications\n\n\nAbstract\nThe Limit
ed Principle of Omniscience (LPO) and Lesser Limited\nPrinciple of Omnisci
ence (LLPO) are frequently included in discussions of\nconstructive mathem
atics. We will compare and contrast the principles using\nideas from Weih
rauch reducibility\, reverse mathematics\, and higher order\nreverse mathe
matics. The preliminary results in higher order reverse\nmathematics are
joint work with Carl Mummert.\n
LOCATION:https://researchseminars.org/talk/CTA/86/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefan Vatev (University of Sofia "St. Kliment Ohridski")
DTSTART:20220427T080000Z
DTEND:20220427T090000Z
DTSTAMP:20260314T091030Z
UID:CTA/87
DESCRIPTION:Title: Eff
ective embeddings for classes of structures via enumeration operators\
nby Stefan Vatev (University of Sofia "St. Kliment Ohridski") as part of C
omputability theory and applications\n\n\nAbstract\nOne can effectivize th
e notion of Borel embedding for classes of structures by considering Turin
g operators or enumeration operators.\nIn this talk\, I will try to argue
that it is interesting to study how these two effective notions of Borel e
mbedding relate to each other \neven if we consider some simple classes of
structures such as pairs of linear orderings\, closed under isomorphism.\
n
LOCATION:https://researchseminars.org/talk/CTA/87/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Clara Löh (University Regensburg)
DTSTART:20221128T130000Z
DTEND:20221128T140000Z
DTSTAMP:20260314T091030Z
UID:CTA/88
DESCRIPTION:Title: $L^
2$-Betti numbers and computability of reals\nby Clara Löh (University
Regensburg) as part of Computability theory and applications\n\n\nAbstrac
t\nFor several real-valued invariants from topology or group theory\, the
individual values are not arbitray real numbers\, but (right-)computable r
eals. For example\, the real numbers arising as $L^2$-Betti numbers of gro
ups are right-computable\, where the right-computability degree is bounded
by the Turing degree of the word problem. \n\nI will give an overview of
such results on $L^2$-Betti numbers and related invariants. This talk is b
ased on joint work with Matthias Uschold.\n
LOCATION:https://researchseminars.org/talk/CTA/88/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Linus Richter (Victoria University Wellington)
DTSTART:20230130T200000Z
DTEND:20230130T210000Z
DTSTAMP:20260314T091030Z
UID:CTA/89
DESCRIPTION:Title: Co-
analytic Counterexamples to Marstrand’s Projection Theorem\nby Linus
Richter (Victoria University Wellington) as part of Computability theory
and applications\n\n\nAbstract\nA recent “point-to-set principle" of J.
Lutz and N. Lutz characterises the Hausdorff dimension of any subset of Eu
clidean space in terms of the complexity of its individual points. “Comp
lexity" here refers to Kolmogorov complexity—so the point-to-set princip
le gives us an algorithmic handle on classical problems in fractal geometr
y: sets with particular fractal properties can now be constructed in stage
s\, point-by-point\, by coding “enough” information into each point\,
bit-by-bit.\nI will give a brief introduction to all these notions\, and p
resent a new result in fractal geometry whose proof uses such effective me
thods: under V=L\, I will outline the construction of co-analytic countere
xamples to Marstrand’s Projection Theorem\, one of fractal geometry’s
seminal theorems about the dimension of orthogonal projections of analytic
plane sets onto lines. Our results also show that Marstrand’s theorem i
s indeed sharp for analytic sets\, a fact previously unknown.\n
LOCATION:https://researchseminars.org/talk/CTA/89/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Valentino Delle Rose (Centro Nacional de Inteligencia Artificial\,
Chile)
DTSTART:20230221T140000Z
DTEND:20230221T150000Z
DTSTAMP:20260314T091030Z
UID:CTA/90
DESCRIPTION:Title: Com
putable PAC learning\nby Valentino Delle Rose (Centro Nacional de Inte
ligencia Artificial\, Chile) as part of Computability theory and applicati
ons\n\n\nAbstract\nPAC (probably approximately correct) learning is a fram
ework for the theoretical analysis of machine learning\, proposed by Valia
nt in 1984. Intuitively\, we consider a certain class of hypotheses: a lea
rner for this class receives a finite amount of random samples of an unkno
wn objective function and\, with high probability\, outputs a function whi
ch approximates the objective function no worse than any hypothesis in the
given class.\nThe fundamental theorem of statistical learning characteriz
es the existence of a learner for a certain class of hypotheses with a com
binatorial property of the class itself\, namely the finiteness of its so-
called VC dimension (Vapnik and Chervonenkis\, 1971\; Blumer et al.\, 1989
).\nHowever\, all this theory deals with learners when simply considered a
s functions\, without taking into account any effectiveness aspect: what d
oes it happen\, then\, when we only focus on learners which can be impleme
nted by some algorithmic procedure?\nTo investigate this question\, Agarwa
l et al. (2020) introduced computable PAC (CPAC) learning\, where both the
learner and the functions it outputs are required to be computable. Their
key observation is that\, in this new framework\, the finiteness of VC di
mension does no longer suffice to ensure the existence of a computable lea
rner. Moreover\, this computable setting is affected by certain aspects wh
ich do not make any difference in classical PAC learning: for example\, wh
ether the learner is required to be proper (i.e. its range must be contain
ed in the class of hypotheses to be learned) or allowed to be improper (i.
e. it can output any function)\, or whether the number of samples the lear
ner needs to actually learn the class is bounded by a computable function.
\nBut which of these aspects actually lead to different versions of comput
able learnability? In this talk\, we will provide a landscape of the field
\, based on previous work of Agarwal et al. (2020)\, Sterkenburg (2022) an
d recent joint work with Alexander Kozachinskiy\, Cristóbal Rojas and Tom
asz Steifer (Pontificia Universidad Católica de Chile).\n
LOCATION:https://researchseminars.org/talk/CTA/90/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Juan Aguilera (Vienna University of Technology)
DTSTART:20230404T100000Z
DTEND:20230404T110000Z
DTSTAMP:20260314T091030Z
UID:CTA/91
DESCRIPTION:Title: Det
erminacy in Second-Order Arithmetic\nby Juan Aguilera (Vienna Universi
ty of Technology) as part of Computability theory and applications\n\n\nAb
stract\nWe survey some recent results on the Reverse Mathematics of determ
inacy principles in Second-Order Arithmetic.\n
LOCATION:https://researchseminars.org/talk/CTA/91/
END:VEVENT
END:VCALENDAR