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:20260404T094532Z
UID:CTA/1
DESCRIPTION:Title: Recursion Theory and Diophantine Approximation\nby Theodore Slaman
(UC Berkeley) as part of Computability theory and applications\n\n\nAbstra
ct\nWe will give a survey of some connections between Recursion Theory\, e
specially Algorithmic Randomness\, and Diophantine Approximation\, especia
lly normality and exponents of irrationality. We will emphasize what we v
iew as the contribution of a recursion theoretic perspective.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julia Knight (Notre Dame)
DTSTART:20200428T120000Z
DTEND:20200428T130000Z
DTSTAMP:20260404T094532Z
UID:CTA/2
DESCRIPTION:Title: Limiting 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 con
jectured that the elementary frst order theory of the random group on n >=
2 generators\, and with a single relator matches\nthat of the non-Abelian
free groups. Coulon\, Ho\, and Logan have proved that the theories match
on universal sentences. We may ask Gromovs question for other varieties. F
ranklin and I looked for varieties for which\ncalculating the limiting den
sities is easier. We have examples for which the elementary frst order the
ory of the random structure matches that of the free structure\, and other
examples for which the theories differ.\n(joint work with Johanna Frankli
n)\n
LOCATION:https://stable.researchseminars.org/talk/CTA/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marta Fiori Carones (LMU Munich)
DTSTART:20200505T200000Z
DTEND:20200505T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/3
DESCRIPTION:Title: A theorem from Rival and Sands and reverse mathematics\nby Marta Fi
ori Carones (LMU Munich) as part of Computability theory and applications\
n\n\nAbstract\nIn 1980 Ivan Rival and Bill Sands proved that for each infi
nite poset P with finite width (i.e. such that there is a fixed finite bou
nd on the size of antichains in P) there is an infinite chain C ⊆ P such
that each element of P is comparable to none or to infinitely many eleme
nts of C. Moreover\, if P is countable\, C can be found such that each ele
ment of P is comparable to none or to cofinitely many elements of C.\nWe
prove that some versions of the previous theorem are equivalent to the Asc
ending/descending sequence principle or to related known principles of the
reverse mathematics zoo. \n(Joint work with Alberto Marcone\, Paul Shafer
and Giovanni Soldà)\n
LOCATION:https://stable.researchseminars.org/talk/CTA/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Denis Hirschfeldt (University of Chicago)
DTSTART:20200519T200000Z
DTEND:20200519T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/4
DESCRIPTION:Title: Minimal pairs in the generic degrees\nby Denis Hirschfeldt (Univers
ity of Chicago) as part of Computability theory and applications\n\n\nAbst
ract\nGeneric computability is a notion of "almost everywhere computabilit
y" that has been studied from a computability-theoretic perspective by sev
eral authors following work of Jockusch and Schupp. It leads naturally to
a notion of reducibility\, and hence to a degree structure. I will discuss
the construction of a minimal pair in the generic degrees\, which contras
ts with Igusa's result that there are\nno minimal pairs for the similar no
tion of relative generic computability. I will then focus on several relat
ed questions that remain open.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Harrison-Trainor (Victoria University of Wellington\, New
Zealand)
DTSTART:20200513T010000Z
DTEND:20200513T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/5
DESCRIPTION:Title: The tree of tuples of a structure\nby Matthew Harrison-Trainor (Vic
toria University of Wellington\, New Zealand) as part of Computability the
ory and applications\n\n\nAbstract\nGiven a countable structure\, one can
associate a tree of finite tuples from that structure\, with each tuple la
beled by its atomic type. This tree encodes the back-and-forth information
of the structure\, and hence determines the isomorphism type\, but it is
still missing something: with Montalban I proved that there are structures
which cannot be computably (or even hyperarithmetically) recovered from t
heir tree of tuples. I'll explain the meaning of this result by exploring
two separate threads in computable structure theory: universality and codi
ng.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dan Turetsky (Victoria University of Wellington\, New Zealand)
DTSTART:20200527T010000Z
DTEND:20200527T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/6
DESCRIPTION:Title: Coding in the automorphism group of a structure\nby Dan Turetsky (V
ictoria University of Wellington\, New Zealand) as part of Computability t
heory and applications\n\n\nAbstract\nIn this talk I will discuss a new te
chnique for coding a closed set into the automorphism group of a structure
. This technique has applications to problems in Scott rank\, effective d
imension\, and degrees of categoricity. For instance\, I will explain how
it can be used to construct a computably categorical structure with nonco
mputable Scott rank.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vittorio Bard (Università degli Studi di Torino)
DTSTART:20200602T140000Z
DTEND:20200602T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/7
DESCRIPTION:Title: A local approach towards uniform Martin’s conjecture\nby Vittorio
Bard (Università degli Studi di Torino) as part of Computability theory
and applications\n\n\nAbstract\nIn 1967 Sacks asked whether there is degre
e invariant r.e. operator that maps x to a solution to Post's problem rela
tivized for x. In 1975\, Lachlan proved that the answer is no if we requir
e the operator to be degree invariant in a uniform way.\nSack's question c
an be considered the forefather of Martin's conjecture\, a foundamental op
en problem that hypothizes that degree invariant functions under AD have l
imited possibilities of behavior. Following Lachlan's example\, in the lat
e 80s Slaman and Steel proved Martin's conjecture for unifromly degree inv
ariant functions.\nWe will show that half of this result is actually the c
onsequence of phenomena that unifromly degree invariant functions already
manisfest on single Turing degrees. We also present a joint result with Pa
trick Lutz\, in which we show that Lachlan's result arises locally\, too.\
n
LOCATION:https://stable.researchseminars.org/talk/CTA/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nikolai Bazhenov (Sobolev Institute of Mathematics)
DTSTART:20200609T140000Z
DTEND:20200609T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/8
DESCRIPTION:Title: Rogers semilattices in the analytical hierarchy\nby Nikolai Bazheno
v (Sobolev Institute of Mathematics) as part of Computability theory and a
pplications\n\n\nAbstract\nFor a countable set S\, a numbering of S is a s
urjective map from ω onto S. A numbering ν is reducible to a numbering
μ if there is a computable function f such that ν(x) = μ f(x) for all i
ndices x. The notion of reducibility between numberings gives rise to a cl
ass of upper semilattices\, which are usually called Rogers semilattices.
We discuss recent results on Rogers semilattices induced by numberings in
the analytical hierarchy. Special attention is given to the first-order pr
operties of Rogers semilattices. The talk is based on joint works with Man
at Mustafa\, Sergei Ospichev\, and Mars Yamaleev.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lu Liu (Central South University)
DTSTART:20200617T010000Z
DTEND:20200617T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/9
DESCRIPTION:Title: The coding power of products of partitions\nby Lu Liu (Central Sout
h University) as part of Computability theory and applications\n\n\nAbstra
ct\nGiven 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 cla
ss of partitions admit two members violating a particular combinatorial co
nstraint. Then we took a digression to see how complex does the class has
to be so as to maintain the cross constraint. \n On the other hand\,
reducing the complexity of the two members in the lemma in certain ways w
ill answer an open question concerning a sort of Weihrauch degree of stabl
e Ramsey's theorem for pairs. It turns out the resulted strengthen of the
lemma is a basis theorem for Pi01 class with additional constraint. We loo
k at several such variants of basis theorem\, among them some are unknown.
\n We end up by introducing some results and questions concerning p
roduct of infinitely many partitions.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sarah Reitzes (University of Chicago)
DTSTART:20200623T200000Z
DTEND:20200623T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/10
DESCRIPTION:Title: Reduction games\, provability\, and compactness\nby Sarah Reitzes
(University of Chicago) as part of Computability theory and applications\n
\n\nAbstract\nIn this talk\, I will discuss joint work with Damir D. Dzhaf
arov and Denis R. Hirschfeldt. Our work centers on the characterization of
problems P and Q such that P is omega-reducible to Q\, as well as problem
s\n P and Q such that RCA_0 proves Q implies P\, in terms of winning strat
egies in certain games. These characterizations were originally introduced
by Hirschfeldt and Jockusch. I will discuss extensions and generalization
s of these characterizations\, including\n a certain notion of compactness
that allows us\, for strategies satisfying particular conditions\, to bou
nd the number of moves it takes to win. This bound is independent of the i
nstance of the problem P being considered.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rod Downey (Victoria University of Wellington)
DTSTART:20200708T010000Z
DTEND:20200708T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/11
DESCRIPTION:Title: Sacks' Splitting Theorem Re-examined (again)\nby Rod Downey (Victo
ria University of Wellington) as part of Computability theory and applicat
ions\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CTA/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mariya Soskova (University of Wisconsin-Madison)
DTSTART:20200714T200000Z
DTEND:20200714T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/12
DESCRIPTION:Title: PA relative to an enumeration oracle\nby Mariya Soskova (Universit
y of Wisconsin-Madison) as part of Computability theory and applications\n
\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CTA/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Amaury Pouly (CNRS)
DTSTART:20200630T140000Z
DTEND:20200630T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/13
DESCRIPTION:Title: A Survey on Analog Models of Computation\nby Amaury Pouly (CNRS) a
s part of Computability theory and applications\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/CTA/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cristóbal Rojas (Universidad Andrés Bello)
DTSTART:20200721T150000Z
DTEND:20200721T160000Z
DTSTAMP:20260404T094532Z
UID:CTA/14
DESCRIPTION:Title: Statistical Chaos — a new barrier in the prediction/simulation of ph
ysical systems\nby Cristóbal Rojas (Universidad Andrés Bello) as par
t of Computability theory and applications\n\n\nAbstract\nIt is well known
that for systems exhibiting “sensitivity to initial conditions”\, it
is practically impossible to predict individual trajectories beyond a very
limited time horizon. To overcome this difficulty\, a statistical approa
ch was developed -- while the computed trajectories are not individually m
eaningful\, when regarded as an ensemble\, their average represents a stat
istical distribution that can be used to make meaningful probabilistic pre
dictions about the system. This statistical paradigm is ubiquitous in mode
rn applications. In this talk we present a new obstacle in applying the s
tatistical approach. We show that the statistical behavior of a parametriz
ed system may exhibit “sensitivity to parameters”\, and that this may
lead to non computability of the limiting\, meaningful\, statistical distr
ibution. We will explain all this in the simplest nonlinear class of syste
ms: quadratic maps of the interval [0\,1]. This is joint work with M. Yamp
olsky.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrew Marks (UCLA)
DTSTART:20200728T210000Z
DTEND:20200728T220000Z
DTSTAMP:20260404T094532Z
UID:CTA/15
DESCRIPTION:Title: Priority arguments in descriptive set theory\nby Andrew Marks (UCL
A) as part 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 a
t at least 3. This characterization is\nproved using Antonio Montalb\\'an'
s true stages machinery for\nconducting priority arguments.\n\nAs an appli
cation\, we prove the decomposability conjecture in\ndescriptive set theor
y assuming projective determinacy. This\nconjecture characterizes precisel
y which Borel functions are\ndecomposable into a countable union of contin
uous functions with\n$\\Pi^0_n$ domains. Our proof also uses a theorem of
Leo Harrington\nthat assuming the axiom of determinacy there is no $\\omeg
a_1$ length\nsequence of distinct Borel sets of bounded rank. This is join
t work\nwith Adam Day.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benoit Monin (LACL/Créteil University)
DTSTART:20200804T140000Z
DTEND:20200804T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/16
DESCRIPTION:Title: Genericity and randomness with ITTMs\nby Benoit Monin (LACL/Créte
il University) as part of Computability theory and applications\n\n\nAbstr
act\nWe will talk about constructibility through the study of Infinite-Tim
e Turing machines. The study of Infinite-Time Turing machines\, ITTMs for
short\, goes back to a paper by Hamkins and Lewis. Informally these machin
es work like regular Turing machines\, with in addition that the time of c
omputation can be any ordinal. Special rules are then defined to specify w
hat happens at a limit step of computation. \n\nThis simple computational
model yields several new non-trivial classes of objects\, the first one be
ing the class of objects which are computable using some ITTM. These class
es have been later well understood and characterized by Welch. ITTMs are n
ot the first attempt of extending computability notions. This was done pre
viously for instance with alpha-recursion theory\, an extension of recursi
on theory to Sigma_1-definability of subsets of ordinals\, within initial
segments of the Godel constructible hierarchy. Even though alpha-recursion
theory is defined in a rather abstract way\, the specialists have a good
intuition of what ``compute'' means in this setting\, and this intuition r
elies on the rough idea of ``some'' informal machine carrying computation
times through the ordinal. ITTMs appeared all the more interesting\, as th
ey consist of a precise machine model that corresponds to part of alpha-re
cursion theory.\n\nRecently Carl and Schlicht used the ITTM model to exten
d algorithmic randomness and effective genericity notions in this setting.
Genericity and randomness are two different approaches to study typical o
bjects\, that is\, objects having ``all the typical properties'' for some
notion of typicality. For randomness\, a property is typical if the class
of reals sharing it is of measure 1\, whereas for genericity\, a property
is typical if the class of reals sharing it is co-meager.\n\nWe will prese
nt a general framework to study randomness and genericity within Godel's c
onstructible hierarchy. Using this framework\, we will present various the
orems about randomness and genericity with respect to ITTMs. We will then
end with a few exciting open questions for which we believe Beller Jensen
and Welch's forcing technique of their book ``coding the universe'' should
be useful.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jun Le Goh (University of Wisconsin)
DTSTART:20200811T140000Z
DTEND:20200811T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/17
DESCRIPTION:Title: Computing descending sequences in linear orderings\nby Jun Le Goh
(University of Wisconsin) as part of Computability theory and applications
\n\n\nAbstract\nLet DS be the problem of computing a descending sequence i
n a given ill-founded linear ordering. We investigate the uniform computat
ional content of DS from the point of view of Weihrauch reducibility\, in
particular its relationship with the analogous problem of computing a path
in a given 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 techniques characterize the problems which have codomain N and are Wei
hrauch reducible to DS\, thereby identifying the so-called first-order par
t of DS.\n\nSecond\, we use the technique of inseparable $\\Pi^1_1$ sets (
first used by Angles d'Auriac\, Kihara in this context) to study the stren
gthening of DS whose inputs are $\\Sigma^1_1$-codes for ill-founded linear
orderings. We prove that this strengthening is still strictly Weihrauch r
educible to choice on Baire space.\n\nThis is joint work with Arno Pauly a
nd Manlio Valenti.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joe Miller (University of Wisconsin)
DTSTART:20200818T200000Z
DTEND:20200818T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/18
DESCRIPTION:Title: Redundancy of information: lowering effective dimension\nby Joe Mi
ller (University of Wisconsin) as part of Computability theory and applica
tions\n\n\nAbstract\nA natural way to measure the similarity between two i
nfinite\nbinary sequences X and Y is to take the (upper) density of their\
nsymmetric difference. This is the Besicovitch distance on Cantor\nspace.
If d(X\,Y) = 0\, then we say that X and Y are coarsely\nequivalent. Greenb
erg\, M.\, Shen\, and Westrick (2018) proved that a\nbinary sequence has e
ffective (Hausdorff) dimension 1 if and only if\nit is coarsely equivalent
to a Martin-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
dimension s>t sequence. Thus\, the\ndifficulty of increasing dimension is
understood.\n\nGreenberg\, et al. also determined the distance from a dime
nsion 1\nsequence to the nearest dimension t sequence. But they left open
the\ngeneral problem of reducing dimension\, which is made difficult by th
e\nfact that the information in a dimension s sequence can be coded (at\nl
east somewhat) redundantly. Goh\, M.\, Soskova\, and Westrick recently\nga
ve a complete solution.\n\nI will talk about both the results in the 2018
paper and the more\nrecent work. In particular\, I will discuss some of th
e coding theory\nbehind these results. No previous knowledge of coding the
ory is\nassumed.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andre Nies (University of Auckland)
DTSTART:20200826T010000Z
DTEND:20200826T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/19
DESCRIPTION:Title: Discovering structure within the class of K-trivial sets\nby Andre
Nies (University of Auckland) as part of Computability theory and applica
tions\n\n\nAbstract\nJoint work with Noam Greenberg\, Joseph Miller\, and
Dan Turetsky\n\nThe K-trivial sets are antirandom in the sense that the in
itial segment complexity in terms of prefix-free Kolmogorov complexity K g
rows as slowly as possible. Chaitin introduced this notion in about 1975\,
and showed that each K-trivial is Turing below the halting set. Shortly a
fter\, Solovay proved that a K-trivial set can be noncomputable. \n\nIn
the past two decades\, many alternative characterisations of this class ha
ve been found: properties such as being low for K\, low for Martin-Löf
(ML) randomness\, and a basis for ML randomness\, which state in one way
or the other that the set is close to computable. \n\nInitially\, the cl
ass of noncomputable K-trivials appeared to be amorphous. More recently\,
evidence of an internal structure has been found. Most of these results c
an be phrased in the language of a mysterious reducibility on the K-trivi
als which is weaker than Turing’s: A is ML-below B if each ML-random com
puting B also computes A.\n\nBienvenu\, Greenberg\, Kucera\, Nies and Ture
tsky (JEMS 2016) showed that there an ML complete K-trivial set. Greenberg
\, Miller and Nies (JML\, 2019) established a dense hierarchy of subcl
asses of the K-trivials based on fragments of Omega computing the set\, an
d each such subclass is an initial segment for ML. More recent results g
eneralise these approaches using cost functions. They also show that each
K-trivial set is ML-equivalent to a c.e. K-trivial. \n\nThe extreme lowne
ss 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 discus
ses open questions. For instance\, is ML-completeness an arithmetical prop
erty of K-trivials?\n
LOCATION:https://stable.researchseminars.org/talk/CTA/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Patrick Lutz (UC Berkeley)
DTSTART:20200901T200000Z
DTEND:20200901T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/20
DESCRIPTION:Title: Part 1 of Martin's Conjecture for Order Preserving Functions\nby P
atrick Lutz (UC Berkeley) as part of Computability theory and applications
\n\n\nAbstract\nMartin's conjecture is an attempt to make precise the idea
that the only natural functions on the Turing degrees are the constant fu
nctions\, the identity\, and transfinite iterates of the Turing jump. The
conjecture is typically divided into two parts. Very roughly\, the first p
art states that every natural function on the Turing degrees is either eve
ntually constant or eventually increasing and the second part states that
the natural functions which are increasing form a well-order under eventua
l domination\, where the successor operation in this well-order is the Tur
ing jump. \n\nIn the 1980's\, Slaman and Steel proved that the second part
of Martin's conjecture holds for order-preserving Borel functions. In joi
nt work with Benny Siskind\, we prove the complementary result that (assum
ing analytic determinacy) the first part of the conjecture also holds for
order-preserving Borel functions (and under AD\, for all order-preserving
functions). Our methods also yield several other new results\, including a
n equivalence between the first part of Martin's conjecture and a statemen
t 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 desc
ribe our new results.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Patrick Uftring (TU Darmstadt)
DTSTART:20200908T140000Z
DTEND:20200908T150000Z
DTSTAMP:20260404T094532Z
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 charact
erize Weihrauch reducibility in E-PAω + QF-AC0\,0 and all systems contain
ing it by the provability in a linear variant of the same calculus using m
odifications of Gödel's Dialectica interpretation that incorporate ideas
from linear logic\, nonstandard arithmetic\, higher-order computability\,
and phase semantics. A full preprint is available here: https://arxiv.org
/abs/2003.13331\n
LOCATION:https://stable.researchseminars.org/talk/CTA/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alberto Marcone (Università di Udine)
DTSTART:20200915T130000Z
DTEND:20200915T140000Z
DTSTAMP:20260404T094532Z
UID:CTA/22
DESCRIPTION:Title: The higher levels of the Weihrauch lattice\nby Alberto Marcone (Un
iversità di Udine) as part of Computability theory and applications\n\n\n
Abstract\nThe classification of mathematical problems in the Weihrauch lat
tice is a line of research that blossomed in the last few years. Initially
this approach dealt mainly with statements which are provable in ACA_0 an
d showed that usually Weihrauch reducibility is more fine-grained than rev
erse mathematics.\n\nIn the last few years the study of multi-valued funct
ions arising 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 tre
e theorem\, comparability of well-orders\, determinacy of open and clopen
games\, König’s duality theorem\, various forms of choice\, the open a
nd clopen Ramsey theorem and the Cantor-Bendixson theorem.\n\nAt this leve
l often a single theorem naturally leads to several multi-valued functions
of different Weihrauch degree\, depending on how the theorem is "read" fr
om a computability 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
uncountably many paths\, or as the request to list all paths of a tree wh
ich does not contain a perfect subtree. Similarly\, the clopen Ramsey theo
rem leads to the multi-valued function that associates to every clopen sub
set 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 ho
mogeneous sets on one side a homogeneous set on that side. Similar functio
ns can be defined similarly starting from the open Ramsey theorem.\n\nIn t
his talk I discuss some of these results\, emphasizing recent joint work w
ith my students Vittorio Cipriani and Manlio Valenti.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Justine Miller (University of Notre Dame)
DTSTART:20200915T200000Z
DTEND:20200915T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/23
DESCRIPTION:Title: Noncomputable Coding\, Density\, and Stochasticity\nby Justine Mil
ler (University of Notre Dame) as part of Computability theory and applica
tions\n\n\nAbstract\nWe introduce the into and within set operations in or
der to construct sets of arbitrary intrinsic density from any Martin-Löf
random. We then show that these operations are useful more generally for w
orking with other notions of density as well\, in particular for viewing C
hurch and MWC stochasticity as a form of density.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Christopher Porter (Drake University)
DTSTART:20200929T200000Z
DTEND:20200929T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/24
DESCRIPTION:Title: Effective Dimension and the Intersection of Random Closed Sets\nby
Christopher Porter (Drake University) as part of Computability theory and
applications\n\n\nAbstract\nThe connection between the effective dimensio
n of sequences and membership in algorithmically random closed subsets of
Cantor space was first identified by Diamondstone and Kjos-Hanssen. In thi
s talk\, I highlight joint work with Adam Case in which we extend Diamonds
tone and Kjos-Hanssen's result by identifying a relationship between the e
ffective dimension of a sequence and what we refer to as the degree of int
ersectability of certain families of random closed sets (also drawing on w
ork 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 no
n-empty intersection varies depending on the choice of underlying probabil
ity measure on the space of closed subsets of Cantor space---this number b
eing the degree of intersectability of a given family of random closed set
s---and (2) the effective dimension of a sequence X is inversely proportio
nal 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
sequence of lower dimension can only be in random closed sets with more br
anching\, which are thus more intersectable\, whereas higher dimension seq
uences can be in random closed sets with less branching\, which are thus l
ess intersectable\, and the relationship between these two quantities (tha
t is\, effective dimension and degree of intersectability) can be given ex
plicitly.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Leszek Kołodziejczyk (University of Warsaw)
DTSTART:20201013T200000Z
DTEND:20201013T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/25
DESCRIPTION:Title: Reverse mathematics of combinatorial principles over a weak base theor
y\nby Leszek Kołodziejczyk (University of Warsaw) as part of Computab
ility theory and applications\n\n\nAbstract\nReverse mathematics studies t
he strength of axioms needed to prove various\nmathematical theorems. Ofte
n\, the theorems have the form $\\forall X \\exists\nY \\psi(X\,Y)$ with $
X\, Y$ denoting subsets of $\\mathbb{N}$ and $\\psi$\narithmetical\, and t
he logical strength required to prove them is closely\nrelated to the diff
iculty of computing $Y$ given $X$. In the early decades\nof reverse mathem
atics\, most of the theorems studied turned out to be\nequivalent\, over a
relatively weak base theory\, to one of just a few typical\naxioms\, whic
h are themselves linearly ordered in terms of strength. More\nrecently\, h
owever\, many statements from combinatorics\, especially Ramsey\ntheory\,
have been shown to be pairwise inequivalent or even logically\nincomparabl
e.\n\nThe usual base theory used in reverse mathematics is $\\mathrm{RCA}_
0$\, which\nis intended to correspond roughly to the idea of "computable m
athematics".\nThe main two axioms of $\\mathrm{RCA}_0$ are: comprehension
for computable\nproperties of natural numbers and mathematical induction f
or c.e.\nproperties. A weaker theory in which induction for c.e. propertie
s is\nreplaced by induction for computable properties has also been introd
uced\,\nbut it has received much less attention. In the reverse mathematic
s\nliterature\, this weaker theory is known as $\\mathrm{RCA}^*_0$.\n\nIn
this talk\, I will discuss some results concerning the reverse mathematics
\nof combinatorial principles over $\\mathrm{RCA}^*_0$. We will focus most
ly on\nRamsey's theorem and some of its well-known special cases: the\ncha
in-antichain principle CAC\, the ascending-descending chain principle ADS\
,\nand the cohesiveness principle COH.\n\nThe results I will talk about ar
e part of a larger project joint with Marta\nFiori Carones\, Katarzyna Kow
alik\, Tin Lok Wong\, and Keita Yokoyama.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Li Ling Ko (University of Notre Dame)
DTSTART:20201027T200000Z
DTEND:20201027T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/26
DESCRIPTION:Title: Fickleness and bounding lattices in the recursively enumerable Turing
degrees\nby Li Ling Ko (University of Notre Dame) as part of Computabi
lity theory and applications\n\n\nAbstract\nThe ability for a recursively
enumerable Turing degree $d$ to bound certain\nimportant lattices depends
on the degree's fickleness. For instance\, $d$\nbounds $L_7$ (1-3-1) if an
d only if $d$'s fickleness is $>\\omega$\n($\\geq\\omega^\\omega$). We wor
k towards finding a lattice that characterizes\nthe $>\\omega^2$ levels of
fickleness and seek to understand the challenges\nfaced in finding such a
lattice. The candidate lattices considered include\nthose that are genera
ted from three independent points\, and upper\nsemilattices that are obtai
ned by removing the meets from important\nlattices.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Paul Shafer (University of Leeds)
DTSTART:20201110T210000Z
DTEND:20201110T220000Z
DTSTAMP:20260404T094532Z
UID:CTA/27
DESCRIPTION:Title: Randomness notions and reverse mathematics\nby Paul Shafer (Univer
sity of Leeds) as part of Computability theory and applications\n\n\nAbstr
act\nThere are many notions of algorithmic randomness in addition to class
ic Martin-Löf randomness\, such as 2-randomness\, weak 2-randomness\, com
putable randomness\, and Schnorr randomness. For each notion of randomnes
s\, 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 arithme
tic\, and we compare the strengths of these principles. We also show that
a well-known characterization of 2-randomness in terms of incompressibili
ty can be proved in RCA_0\, which is non-trivial because it requires avoid
ing the use of $\\Sigma^0_2$ bounding.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Karen Lange (Wellesley College)
DTSTART:20201124T210000Z
DTEND:20201124T220000Z
DTSTAMP:20260404T094532Z
UID:CTA/28
DESCRIPTION:Title: Complexity of root-taking in power series fields & related problems\nby Karen Lange (Wellesley College) as part of Computability theory and
applications\n\n\nAbstract\nIn earlier work with Knight and Solomon\, we b
ounded the computational complexity of the root-taking process over Puiseu
x and Hahn series\, two kinds of generalized power series. But it is open
whether the bounds given are optimal. By looking at the most basic steps i
n the root-taking process for Hahn series\, we together with Hall and Knig
ht became interested in the complexity of problems associated with well-or
dered subsets of a fixed ordered abelian group. Here we provide an overvie
w of the results so far in both these settings.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Linda Brown Westrick (Penn State)
DTSTART:20201208T210000Z
DTEND:20201208T220000Z
DTSTAMP:20260404T094532Z
UID:CTA/29
DESCRIPTION:Title: Luzin's (N) and randomness reflection\nby Linda Brown Westrick (Pe
nn State) as part of Computability theory and applications\n\n\nAbstract\n
We 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 reflec
ts Kurtz 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-r
andom as well. If additionally f is known to have bounded variation\, then
we show 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 link
s classical real analysis with algorithmic randomness. Joint with Arno Pa
uly and Liang Yu.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Timothy McNicholl (Iowa State University)
DTSTART:20200923T000000Z
DTEND:20200923T010000Z
DTSTAMP:20260404T094532Z
UID:CTA/30
DESCRIPTION:Title: Which Lebesgue spaces are computably presentable?\nby Timothy McNi
choll (Iowa State University) as part of Computability theory and applicat
ions\n\n\nAbstract\nWe consider the following question: ``If there is a co
mputably 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 the field of scalars. So\, we turn to non-trivial cases. Namely\,
assume there 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 sho
w there is no uniform solution of this problem even when given upper and l
ower bounds on the exponent. The proof of this result leads to some basic
results on the effective theory of stable random variables. Finally\, we
conjecture 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://stable.researchseminars.org/talk/CTA/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Paul-Elliot Angles d'Auriac (University of Lyon)
DTSTART:20201006T130000Z
DTEND:20201006T140000Z
DTSTAMP:20260404T094532Z
UID:CTA/31
DESCRIPTION:Title: The computable strength of Milliken's Tree Theorem and applications\nby Paul-Elliot Angles d'Auriac (University of Lyon) as part of Computab
ility theory and applications\n\n\nAbstract\nDevlin's theorem and the Rado
graph theorem are both variants of Ramsey's theorem\, where a structure i
s added but more colors are allowed: Devlin's theorem (respectively the Ra
do graph theorem) states if S is ℚ (respectively G\, the Rado graph)\, t
hen 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 subco
py of S on which the coloring takes at most l colors. Moreover\, given n\,
the optimal l is specified.\n\nThe key combinatorial theorem used in both
the proof of Devlin's theorem and the Rado graph theorem is Milliken's tr
ee theorem. Milliken's tree theorem is also a variant of Ramsey's theorem\
, but this time for trees and strong subtrees: it states that given a colo
ring of the strong subtrees of height n of a tree T\, there exists a stron
g subtree 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
results on the computable strength of Milliken's tree theorem and its app
lications Devlin and the Rado graph theorem\, obtained with Cholak\, Dzhaf
arov\, Monin and Patey.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexandra Soskova (Sofia University)
DTSTART:20201020T140000Z
DTEND:20201020T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/32
DESCRIPTION:Title: Effective embeddings and interpretations\nby Alexandra Soskova (So
fia University) as part of Computability theory and applications\n\n\nAbst
ract\nFriedman and Stanley introduced Borel embeddings as a way of compari
ng classification problems for different classes of structures. Many Bor
el embeddings are actually Turing computable. The effective decoding is gi
ven by a uniform effective interpretation. Part of the effective interpre
tation is actually Medvedev reduction. \nThe class of undirected graphs a
nd the class of linear orderings both lie on top under Turing computable e
mbeddings. We give examples of graphs that are not Medvedev reducible to
any linear ordering\, or to the jump of any linear ordering. For any grap
h\, there is a linear ordering\, that the graph is Medvedev reducible to t
he second jump of the linear ordering. Friedman and Stanley gave a Turing
computable embedding $L$ of directed graphs in linear orderings. We show
that there do not exist $L_{\\omega_1\\omega}$-formulas that uniformly in
terpret the input graph $G$ in the output linear ordering $L(G)$. This is
joint work with Knight\, and Vatev.\n\nWe have also one positive result --
- we prove that the class of fields is uniformly effectively interpreted w
ithout parameters in the class of Heisenberg groups.\nThe second part is
joint work with Alvir\, Calvert\, Goodman\, Harizanov\, Knight\, Miller\
, Morozov\, and Weisshaar.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chris Conidis (CUNY-College of Staten Island)
DTSTART:20201014T010000Z
DTEND:20201014T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/33
DESCRIPTION:Title: Non-arithmetic algebraic constructions\nby Chris Conidis (CUNY-Col
lege of Staten Island) as part of Computability theory and applications\n\
n\nAbstract\nWe examine two radical constructions\, one from ring theory a
nd another from module theory\, and produce a computable ring for each con
struction where the corresponding radical is $\\Pi^1_1$-complete.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Manlio Valenti (Università di Udine)
DTSTART:20201103T140000Z
DTEND:20201103T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/34
DESCRIPTION:Title: On the descriptive complexity of Fourier dimension and Salem sets\
nby Manlio Valenti (Università di Udine) as part of Computability theory
and applications\n\n\nAbstract\nIt is known that\, for Borel sets\, the Fo
urier dimension is less than or equal to the Hausdorff dimension. The sets
for which the two notions agree are called Salem sets.\n\nIn this talk\,
we explore the descriptive complexity of the family of closed Salem subset
s of the Euclidean space. We also show how these results yield a character
ization of the Weihrauch degree of the maps computing the Hausdorff or the
Fourier dimensions.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laurent Bienvenu (Université de Bordeaux)
DTSTART:20201110T140000Z
DTEND:20201110T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/35
DESCRIPTION:Title: The interplay between randomness and genericity\nby Laurent Bienve
nu (Université de Bordeaux) as part of Computability theory and applicati
ons\n\n\nAbstract\nIn computability theory\, one often think of (Cohen)-ge
nericity and algorithmic randomness as orthogonal notions: a truly random
real will look very non-generic\, and a truly generic real will look very
non-random. This orthogonality is best incarnated by the result of Nies\,
Stephan and Terwijn that any 2-random real and 2-generic real form a minim
al pair for Turing reducibility. On the other hand\, we know from the Kuce
ra-Gacs theorem that for any n there is a 1-random real which computes an
n-generic one\, but also (and more surprisingly)\, by a result of Kautz th
at every 2-random real computes a 1-generic real. These last two results t
ell us that the interplay between randomness and genericity is rather comp
lex when “randomness” is between 1-random and 2-random or “genericit
y” between 1-generic and 2-generic. It is this gray area that we will di
scuss in this talk (based on the paper of the same title\, joint work with
Chris Porter).\n
LOCATION:https://stable.researchseminars.org/talk/CTA/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bjørn Kjos-Hanssen (University of Hawaii at Manoa)
DTSTART:20201117T230000Z
DTEND:20201118T000000Z
DTSTAMP:20260404T094532Z
UID:CTA/36
DESCRIPTION:Title: A family of metrics connecting Jaccard distance to normalized informat
ion distance\nby Bjørn Kjos-Hanssen (University of Hawaii at Manoa) a
s part of Computability theory and applications\n\n\nAbstract\nDistance me
trics are used in a wide variety of scientific contexts. In a 2001 paper i
n the journal Bioinformatics\, M. Li\, Badger\, Chen\, Kwong\, and Kearney
introduced 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 the
y call the normalized information distance (NID). Raff and Nicholas (2017)
proposed a return to the Bioinformatics distance\, based on further appli
cation-informed criteria.\n\nWe attempt to shed some light on this "disput
e" by showing that the Jaccard distance and the NID analogue form the extr
eme points of the set of metrics within a family of semimetrics studied by
Jiménez\, Becerra\, and Gelbukh (2013).\n\nThe NID is based on Kolmogoro
v complexity\, and Terwijn\, Torenvliet and Vitányi (2011) showed that it
is neither upper semicomputable nor lower semicomputable. Our result give
s a 2-dimensional family including the NID as an extreme point. It would b
e interesting to know if any of these functions are semicomputable.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Keita Yokoyama (Japan Advanced Institute of Science and Technology
)
DTSTART:20201216T003000Z
DTEND:20201216T013000Z
DTSTAMP:20260404T094532Z
UID:CTA/37
DESCRIPTION:Title: Automorphism argument and reverse mathematics\nby Keita Yokoyama (
Japan Advanced Institute of Science and Technology) as part of Computabili
ty theory and applications\n\n\nAbstract\nIn the study of models of Peano
(or first-order) arithmetic\, there are\nmany results on recursively satur
ated models and their automorphisms.\nHere\, we apply such an argument to
models of second-order arithmetic\nand see that any countable recursively
saturated model (M\,S) of WKL_0*\nis isomorphic to its countable coded ome
ga-submodel if\nSigma_1-induction fails in (M\,S). From this result\, we s
ee some\ninteresting but weird properties of WKL_0* with the absence of\nS
igma_1-induction such as the collapse of analytic hierarchy. This\nargumen
t can also be applied to the reverse mathematical study of\nRamsey's theor
em for pairs (RT22)\, and we see some new relations\nbetween the computabi
lity-theoretic characterizations of RT22 and the\nfamous open question on
the first-order part of RT22+RCA_0.\nThis work is a part of a larger proje
ct joint with Marta Fiori\nCarones\, Leszek Kolodziejczyk\, Katarzyna Kowa
lik and Tin Lok Wong.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Emanuele Frittaion (TU Darmstadt)
DTSTART:20210119T090000Z
DTEND:20210119T100000Z
DTSTAMP:20260404T094532Z
UID:CTA/38
DESCRIPTION:Title: Generic realizability for intuitionistic set theory\nby Emanuele F
rittaion (TU Darmstadt) as part of Computability theory and applications\n
\n\nAbstract\nGeneric realizability goes back to Kreisel's and Troelstra's
interpretation of intuitionistic second order arithmetic. It was later ad
apted to systems of intuitionistic set theory by Friedman\, Beeson\, McCar
thy\, and Rathjen. We survey known applications and present some recent on
es. Joint with Michael Rathjen and Takako Nemoto.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Giovanni Soldà (University of Leeds)
DTSTART:20210126T150000Z
DTEND:20210126T160000Z
DTSTAMP:20260404T094532Z
UID:CTA/39
DESCRIPTION:Title: Rival-Sands principles in the Weihrauch degrees\nby Giovanni Sold
à (University of Leeds) as part of Computability theory and applications\
n\n\nAbstract\nwRSg and wRSgr are consequences of RSg\, a theorem about gr
aphs proved in 1980 by Rival and Sands. wRSg and wRSgr can be shown to be
equivalent to Ramsey theorem for pairs over RCA_0\, but are computationall
y strictly weaker. In this talk\, we will study the Weihrauch degrees asso
ciated to these principles\, by comparing them with the degrees of other c
lassical theorems introduced in the analysis of RT22. This is a joint work
with Marta Fiori Carones and Paul Shafer.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Verónica Becher (Universidad de Buenos Aires)
DTSTART:20210309T170000Z
DTEND:20210309T180000Z
DTSTAMP:20260404T094532Z
UID:CTA/40
DESCRIPTION:Title: Open questions on randomness and uniform distribution\nby Veróni
ca Becher (Universidad de Buenos Aires) as part of Computability theory an
d applications\n\n\nAbstract\nHow is Martin-Löf randomness for real numbe
rs related to the classical theory of uniform distribution? In this talk
I review several results on this relation and I present several open que
stions.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Victor Selivanov (Institute of Informatics Systems\, Novosibirsk)
DTSTART:20210209T130000Z
DTEND:20210209T140000Z
DTSTAMP:20260404T094532Z
UID:CTA/41
DESCRIPTION:Title: Primitive recursive ordered fields and some applications\nby Victo
r Selivanov (Institute of Informatics Systems\, Novosibirsk) as part of Co
mputability theory and applications\n\n\nAbstract\nWe establish primitive
recursive versions of some known facts about computable ordered fields of
reals and the field of computable reals and then apply them to some proble
ms in linear algebra and analysis. In particular\, we find a partial primi
tive recursive analog of Ershov-Madison’s theorem about real closures of
computable ordered fields\, relate the corresponding fields to the primit
ive recursive reals\, give sufficient conditions for primitive recursive r
oot-finding\, computing normal forms of matrices\, and computing solution
operators of some linear systems of PDE.\nThis is joint work with Svetlana
Selivanova.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Arno Pauly (Swansea University)
DTSTART:20210201T213000Z
DTEND:20210201T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/42
DESCRIPTION:Title: The structure of Weihrauch degrees - what we know and what we don't kn
ow\nby Arno Pauly (Swansea University) as part of Computability theory
and applications\n\n\nAbstract\nThe Weihrauch degrees are a popular setti
ng for classifying the computational content of mathematical theorems. Und
erstanding their structure is useful as technical tool in concrete classif
ications. Moreover\, their structure tells us something about how degrees
of non-computability look like in principle. In this talk\, I'll summarize
what is already known about the structure of the Weihrauch degrees\, and
try to draw attention to some open problems. For example. we know that the
y form a distributive lattice\, which is not a Heyting algebra and which i
s not complete. We have further natural algebraic operations\, and we know
of a few that they are definable in terms of others. The Medvedev degrees
embed into the Weihrauch degrees as a lattice\, as do the many-one degree
s (but in a weird way).\n
LOCATION:https://stable.researchseminars.org/talk/CTA/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Verónica Becher (Universidad de Buenos Aires)
DTSTART:20210215T213000Z
DTEND:20210215T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/43
DESCRIPTION:Title: Normal numbers and perfect necklaces\nby Verónica Becher (Univers
idad de Buenos Aires) as part of Computability theory and applications\n\n
\nAbstract\nThe most famous example of a normal number is Champernowne's c
onstant 0.123456789101112… Although the definition is very simple\, the
original proof of normality requires quite some work. In this talk I prese
nt "perfect necklaces"\, a combinatorial object that yields a simple proof
of Champernowne's normality result. And with a class of them\, the "neste
d perfect necklaces"\, I explain M. Levin's constant\, the number with the
fastest known speed of convergence to normality.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kirsten Eisenträger (The Pennsylvania State University)
DTSTART:20210301T213000Z
DTEND:20210301T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/44
DESCRIPTION:Title: A topological approach to undefinability in algebraic extensions of th
e rationals\nby Kirsten Eisenträger (The Pennsylvania State Universit
y) as part of Computability theory and applications\n\n\nAbstract\nIn 1970
Matiyasevich proved that Hilbert’s Tenth Problem over the\nintegers is
undecidable\, building on work by Davis-Putnam-Robinson. Hilbert’s\nTent
h Problem over the rationals is still open\, but it could be resolved by\n
giving an existential definition of the integers inside the rationals. Pro
ving\nwhether such a definition exists is still out of reach. However\, we
will show\nthat only “very few” algebraic extensions of the rationals
have the property\nthat their ring of integers are existentially or unive
rsally definable.\nEquipping the set of all algebraic extensions of the ra
tionals with a natural\ntopology\, we show that only a meager subset has t
his property. An important tool\nis a new normal form theorem for existent
ial definitions in such extensions. As\na corollary\, we construct countab
ly many distinct computable algebraic\nextensions whose rings of integers
are neither existentially nor universally\ndefinable. Joint work with Russ
ell Miller\, Caleb Springer\, and Linda Westrick.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chris Conidis (CUNY College of Staten Islan)
DTSTART:20210315T203000Z
DTEND:20210315T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/45
DESCRIPTION:Title: The Reverse Mathematics of Noether's Decomposition Lemma\nby Chris
Conidis (CUNY College of Staten Islan) as part of Computability theory an
d applications\n\n\nAbstract\nWe will survey some recent results in the Re
verse Mathematics of Noetherian Algebra\, and in particular Noether's Deco
mposition Lemma which states that a Noetherian ring has only finitely many
minimal prime ideals. Such an analysis naturally leads one to formulate a
combinatorial principle\, namely the Tree-Antichain Principle\, which sta
tes that every binary-branching tree with infinitely many splittings has a
n infinite antichain.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julia Knight (University of Notre Dame)
DTSTART:20210405T203000Z
DTEND:20210405T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/46
DESCRIPTION:Title: Describing structures and classes of structures\nby Julia Knight (
University of Notre Dame) as part of Computability theory and applications
\n\n\nAbstract\nThe talk will recall some definitions and results on Scott
complexity of individual countable structures\, Borel complexity of class
es of structures\, and Borel cardinality\, for comparing classification pr
oblems for different classes. I will try to indicate how methods from comp
utability may sometimes be used in this connection\, even for results that
do not mention computability. I will state some results on torsion-free A
belian groups\, due to Downey-Montalbán\, Hjorth\, Thomas\, and Paolini-S
helah. Finally\, I will mention a project with Turbo Ho and Russell Miller
\, saying what we would like to do\, but have not done.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noam Greenberg (Victoria University of Wellington)
DTSTART:20210419T203000Z
DTEND:20210419T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/47
DESCRIPTION:Title: The strength of Borel Wadge comparability\nby Noam Greenberg (Vict
oria University of Wellington) as part of Computability theory and applica
tions\n\n\nAbstract\nWadge’s comparability lemma says that the Borel set
s are almost 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 continu
ous pre-image of the complement of A. Wadge’s proof uses Borel determina
cy\, which is not provable in second order arithmetic (H. Friedman). Using
deep and 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 a
iming to clarify this.\n\nOne of the main technical tools we use is Montal
bán’s “true stage” machinery\, originally developed for iterated pr
iority constructions in computable structure theory\, but more recently us
ed by Day and Marks for their resolution of the decomposability conjecture
.\n\nJoint work with Adam Day\, Matthew Harrison-Trainor\, and Dan Turetsk
y.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andre Nies (Auckland University)
DTSTART:20210503T203000Z
DTEND:20210503T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/48
DESCRIPTION:Title: Maximal towers and ultrafilter bases in computability theory\nby A
ndre Nies (Auckland University) as part of Computability theory and applic
ations\n\n\nAbstract\nThe tower number and ultrafilter numbers are cardina
l characteristics from set theory that are defined in terms of sets of nat
ural numbers with almost inclusion. The former is the least size of a maxi
mal tower. The latter is the least size of a collection of infinite sets w
ith upward closure a non-principal ultrafilter. \n\nTheir analogs in compu
tability theory will be defined in terms of collections of computable sets
\, given as the columns of a single set. We study their complexity using M
edvedev reducibility. For instance\, we show that the ultrafilter number i
s Medvedev equivalent to the problem of finding a function that dominates
all computable functions\, that is\, highness. In contrast\, each nonlow s
et uniformly computes a maximal tower. \n\nJoint work with Steffen Lempp\,
Joseph Miller\, and Mariya Soskova\n
LOCATION:https://stable.researchseminars.org/talk/CTA/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mathieu Hoyrup (LORIA)
DTSTART:20210202T150000Z
DTEND:20210202T160000Z
DTSTAMP:20260404T094532Z
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\nE
rshov's generalization of Kleene's recursion theorem is a fixed-point theo
rem for computable multi-valued functions on numbered sets. We study its c
ontinuous version for continuous multi-valued functions on represented spa
ces. We obtain results explaining why the fixed-point theorem usually hold
s uniformly and why in most cases it can only be proved by the diagonal ar
gument. We investigate restricted classes of spaces\, for which we give a
complete characterization of the spaces with the fixed-point property: the
countably-based spaces and the spaces of open sets. We also give an appli
cation to the base-complexity classification of topological spaces.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeff Hirst (Appalachian State University)
DTSTART:20210223T200000Z
DTEND:20210223T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/50
DESCRIPTION:Title: Current thoughts on Hindman’s Theorem\nby Jeff Hirst (Appalachia
n State University) as part of Computability theory and applications\n\n\n
Abstract\nThe exact reverse mathematical strength of Hindman’s theorem i
s a long standing open question. This talk will discuss efforts to carry
out an ultrafilter-based proof using only arithmetical comprehension. A p
articular emphasis is the definability of a class of sets that witness tha
t certain ultrafilters do not encode homogeneous sets for Hindman’s theo
rem.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luca San Mauro (Institute for Discrete Mathematics and Geometry)
DTSTART:20210302T130000Z
DTEND:20210302T140000Z
DTSTAMP:20260404T094532Z
UID:CTA/51
DESCRIPTION:Title: Classifying word problems\nby Luca San Mauro (Institute for Discre
te Mathematics and Geometry) as part of Computability theory and applicati
ons\n\n\nAbstract\nThe study of word problems dates back to the work of De
hn in \n1911. Given a recursively presented algebra A\, the word problem o
f A is \nto decide if two words in the generators of A refer to the same e
lement. \nNowadays\, much is known about the complexity of word problems f
or \nalgebraic structures: e.g.\, the Novikov-Boone theorem – one of the
most \nspectacular applications of computability to general mathematics
– \nstates that the word problem for finitely presented groups is \nunso
lvable. Yet\, the computability theoretic tools commonly employed to \nmea
sure the complexity of word problems (e.g.\, Turing or m-reducibility) \na
re defined for sets\, while it is generally acknowledged that many \ncompu
tational facets of word problems emerge only if one interprets them \nas e
quivalence relations.\nIn this work\, we revisit the world of word problem
s through the lens of \nthe theory of equivalence relations\, which has gr
own immensely in recent \ndecades. To do so\, we employ computable reducib
ility\, a natural \neffectivization of Borel reducibility.\nThis is joint
work with Valentino Delle Rose and Andrea Sorbi.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Steffen Lempp (University of Wisconsin-Madison)
DTSTART:20210331T010000Z
DTEND:20210331T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/52
DESCRIPTION:Title: Decidability and Undecidability in the Enumeration Degrees\nby Ste
ffen Lempp (University of Wisconsin-Madison) as part of Computability theo
ry and applications\n\n\nAbstract\nFor most “natural” degree structure
s\, the full first-order theory (in the language of partial ordering) is a
s complicated 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 f
rom the AE-theory to the EAE-theory.\nI will survey some of the results fr
om the 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 degr
ees: By proving a strong embedding result for finite distributive lattices
into intervals of the enumeration degrees\, we obtain the undecidability
of the EAE-theory\, and a partial decidability result for the AE-theory\,
namely\, for the extension of embeddings problem.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Iskander Kalimullin (Kazan (Volga Region) Federal University)
DTSTART:20210323T140000Z
DTEND:20210323T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/53
DESCRIPTION:Title: Punctual categoricity and degrees of punctual categoricity for finitel
y generated structures.\nby Iskander Kalimullin (Kazan (Volga Region)
Federal University) as part of Computability theory and applications\n\n\n
Abstract\nA punctual algebraic structure A (i.e.\, primitive recursive str
ucture on the universe $\\omega$) is punctually categorical if for every i
ts punctual copy B there is an isomorphism from A onto B which is primitiv
e recursive together with the inverse. We note that there is an unexpected
dichotomy for this notion: every punctually categorical structure is eith
er finitely generated\, or locally finite. This dichotomy also holds for t
he structures which have a degree of punctual categoricity. For the finite
ly generated structures we can describe the possible degrees of punctual c
ategoricity. We have some partial results relating degrees of punctual cat
egoricity of locally finite structures. The results obtained jointly with
Alexander Melnikov.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Merlin Carl (Europa-Universität Flensburg)
DTSTART:20210406T080000Z
DTEND:20210406T093000Z
DTSTAMP:20260404T094532Z
UID:CTA/54
DESCRIPTION:Title: Complexity and Decision Times for ITTMs - The Story of the Bold Conjec
ture\nby Merlin Carl (Europa-Universität Flensburg) as part of Comput
ability theory and applications\n\n\nAbstract\nInfinite Time Turing Machin
es (ITTMs)\, defined in the classical paper by Hamkins and Lewis\, allow T
uring machines to run for transfinite ordinal time. One can then generaliz
e notions of time (Schindler) and space (Löwe) complexity to this setting
. Löwe's "bold conjecture" was whether the two notions are non-trivially
connected\, i.e.\, whether low space complexity implies low time complexit
y. In our talk\, we will show that this conjecture fails. Showing this wil
l\, however\, leads naturally to a systematics study of decision and semi-
decision times on ITTMs\, which was done in joint work with Philipp Schlic
ht and Philip Welch and led to connections with descriptive set theory and
generalizations to the theory of ranks.\n\nJoint work with Philipp Schlic
ht and Philip Welch.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Belanger (National University of Singapore)
DTSTART:20210413T080000Z
DTEND:20210413T090000Z
DTSTAMP:20260404T094532Z
UID:CTA/55
DESCRIPTION:Title: Maximal order types of well partial orders\nby David Belanger (Nat
ional University of Singapore) as part of Computability theory and applica
tions\n\n\nAbstract\nWe outline a general approach for computing (bounds o
n) maximal order types of certain well partial orders. This is part of an
ongoing project to generalize and extend work of van der Meeren characteri
sing the Bachmann-Howard ordinal as such an order type. Joint with Andreas
Weiermann.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vasco Brattka (Universität der Bundeswehr München)
DTSTART:20210420T160000Z
DTEND:20210420T173000Z
DTSTAMP:20260404T094532Z
UID:CTA/56
DESCRIPTION:Title: The Discontinuity Problem\nby Vasco Brattka (Universität der Bund
eswehr München) as part of Computability theory and applications\n\n\nAbs
tract\nWe introduce the discontinuity problem and we prove that under the
axiom of determinacy it is actually the weakest discontinuous problem in t
he topological Weihrauch lattice. We also discuss algebraic properties of
the discontinuity problem\, such as the fact that it parallelizes to the n
on-computability problem. We also introduce an operation that we call stas
hing and show that is dual to parallelization. We show that the discontinu
ity problem is the stashing of LLPO and several variants of it.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Liang Yu (Nanjing University)
DTSTART:20210603T010000Z
DTEND:20210603T023000Z
DTSTAMP:20260404T094532Z
UID:CTA/57
DESCRIPTION:Title: Some consequences of TD and sTD.\nby Liang Yu (Nanjing University)
as part of Computability theory and applications\n\n\nAbstract\nTD says t
hat for every cofinal set $A$ of \\emph{Turing degrees}\, $A$ contains an
upper cone\; and sTD says that for every set $A$ of \\emph{reals} with cof
inal range in the Turing degrees\, $A$ has a pointed subset (a pointed set
is a perfect set in which every real computes a representation of the set
). We prove some consequences of TD and sTD. For example\, we prove that s
TD implies for every set of reals\, its Hausdorff dimension can be approxi
mated by it closed subsets.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pavel Semukhin (University of Oxford)
DTSTART:20210608T130000Z
DTEND:20210608T140000Z
DTSTAMP:20260404T094532Z
UID:CTA/58
DESCRIPTION:Title: The Membership Problem for 2x2 integer matrices\nby Pavel Semukhin
(University of Oxford) as part of Computability theory and applications\n
\n\nAbstract\nThe Membership Problem for matrix semigroups is stated as fo
llows: given a finite collection of square matrices F = { M_1\,...\,M_k }
and a target matrix M\, decide if M can be presented as a product of matri
ces from F. In other words\, decide if M belongs to the semigroup gene
rated by F. It has been known for a long time that the Membership Problem
is undecidable for 3x3 matrices. On the other hand\, it is a big open ques
tion whether this problem is decidable for 2x2 matrices or for some specia
l cases of 3x3 matrices.\n\nIn our recent work\, we showed that the Member
ship Problem is decidable for 2x2 nonsingular integer matrices. In this ta
lk\, I will present a proof of this result which is based on a combination
of different ideas from linear algebra\, group theory\, and automata theo
ry.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/58/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rachael Alvir (University of Notre Dame)
DTSTART:20210913T203000Z
DTEND:20210913T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/59
DESCRIPTION:Title: Finitely α-generated Structures\nby Rachael Alvir (University of
Notre Dame) as part of Computability theory and applications\n\n\nAbstract
\nIn this talk\, we define the notion of a finitely α-generated structure
and generalize results about Scott sentences earlier known only for finit
ely generated structures. We will show how these results can be used to th
e connect some of the existing non-equivalent definitions of Scott rank.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Josiah Jacobsen-Grocott (University of Wisconsin)
DTSTART:20210913T210000Z
DTEND:20210913T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/60
DESCRIPTION:Title: A Characterization of the Strongly η-Representable Many-One Degrees\nby Josiah Jacobsen-Grocott (University of Wisconsin) as part of Comput
ability theory and applications\n\n\nAbstract\nη-representations are a wa
y of coding sets in computable linear orders that were first introduced by
Fellner in his thesis. Limitwise monotonic functions have been used to ch
aracterize the sets with η-representations and give characterizations for
several variations of η-representations. The one exception is the class
of sets with strong η-representations\, the only class where the order ty
pe of the representation is unique. We introduce the notion of a connected
approximation of a set\, a variation on Σ02 approximations. We use conne
cted approximations to give a characterization of the many-one degrees of
sets with strong η-representations as well as new characterizations of th
e variations of η-representations with known characterizations.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/60/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benoit Monin (Créteil University)
DTSTART:20210927T203000Z
DTEND:20210927T213000Z
DTSTAMP:20260404T094532Z
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 applicatio
ns\n\n\nAbstract\nThe Milliken’s tree theorem is an extension of Ramsey
’s theorem to trees. It implies for instance that if we assign to all th
e sets of two strings of the same length\, one among k colors\, there is a
n infinite binary tree within which every pair of strings of the same leng
th has the same color. We are going to present some results on Milliken’
s tree theorem from the viewpoint of computability theory and reverse math
ematics.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/61/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vittorio Cipriani (University of Udine)
DTSTART:20211011T203000Z
DTEND:20211011T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/62
DESCRIPTION:Title: Cantor-Bendixson Theorem in the Weihrauch lattice\nby Vittorio Cip
riani (University of Udine) as part of Computability theory and applicatio
ns\n\n\nAbstract\nIn this talk we will study the Cantor-Bendixson theorem
using the\nframework of Weihrauch reducibility. (Variations of) this theor
em falls into\nthe highest of the big-five axiom systems of reverse mathem
atics\, namely\n\\Pi_1^1-CA_0 . Kihara\, Marcone and Pauly already showed
that many problems\nrepresenting principles equivalent to ATR_0 lie in dif
ferent Weihrauch\ndegrees\, for \\Pi_1^1-CA_0 we actually have a natural c
andidate\, namely the one\nmapping a countable sequence of trees to the ch
aracteristic function of the\nset of indices corresponding to well-founded
trees. This principle was firstly\nconsidered by Hirst\, that also showed
its Weihrauch equivalence with PK_Tr\,\nthe function that takes as input
a tree and outputs its perfect kernel for\ntrees. Even if in reverse mathe
matics it is actually equivalent to consider\ntrees or closed sets\, we wi
ll show that PK_Tr <_W PK_X\, where PK_X takes as\ninput a closed set of a
computable Polish space X and outputs its perfect\nkernel. The equivalenc
e between these two shows up if we switch to\narithmetical Weihrauch reduc
ibility.\n\nWe will continue in this direction showing (non) reductions be
tween problems\nrelated to the Cantor-Bendixson theorem with particular at
tention paid to\nclassify them for every computable Polish space X. This l
eads us to the result\nthat\, while PK_X and wCB_X (i.e. same as PK_X but
where the 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 o
f the scattered part) "almost"\nsplits in two Weihrauch degrees\, one havi
ng as representative PK_X and the\nother having CB_\\Baire.\n\nThis is joi
nt work with Alberto Marcone and Manlio Valenti.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/62/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Webb (University of Hawaiʻi at Mānoa)
DTSTART:20211011T210000Z
DTEND:20211011T213000Z
DTSTAMP:20260404T094532Z
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://stable.researchseminars.org/talk/CTA/63/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sarah Reitzes (University of Chicago)
DTSTART:20211025T203000Z
DTEND:20211025T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/64
DESCRIPTION:Title: Comparing induction and bounding principles over RCA0 and RCA*0\nb
y Sarah Reitzes (University of Chicago) as part of Computability theory an
d applications\n\n\nAbstract\nIn this talk\, I will discuss joint work wit
h Damir D. Dzhafarov and Denis R. Hirschfeldt\, and more recent work follo
wing that line of research. Our work centers on the characterization of re
ductions between Π12 problems P and Q in terms of winning strategies in c
ertain games. These characterizations were originally introduced by Hirsch
feldt and Jockusch in [1]. I will discuss extensions and generalizations o
f these characterizations\, including a certain notion of compactness that
allows us\, for strategies satisfying particular conditions\, to bound th
e number of moves it takes to win. This bound is independent of the instan
ce of the problem P being considered. This allows us to develop the idea o
f Weihrauch and generalized Weihrauch reduction over some base theory. Her
e\, we will focus on the base theory RCA0 and the weaker system RCA*0. In
this talk\, I will explore these notions of reduction among various princi
ples\, including bounding and induction principles. I will present a metat
heorem that allows us to obtain many nonreductions between these principle
s. \n\n[1] D. R. Hirschfeldt and C. G. Jockusch\, Jr.: On notions of compu
tability-theoretic reduction between Π12 principles. Journal of Mathemati
cal Logic 16 (1650002)\, 59 pp. (2016)\n
LOCATION:https://stable.researchseminars.org/talk/CTA/64/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Diego Rojas (Iowa State University)
DTSTART:20211025T210000Z
DTEND:20211025T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/65
DESCRIPTION:Title: Effective convergence notions for measures on the real line\nby Di
ego Rojas (Iowa State University) as part of Computability theory and appl
ications\n\n\nAbstract\nIn classical measure theory\, there are two primar
y convergence notions studied for sequences of measures: weak and vague co
nvergence. In this talk\, we discuss a framework to study the effective th
eory of weak and vague convergence of measures on the real line. For effec
tive weak convergence\, we give an effective version of a characterization
theorem for weak convergence called the Portmanteau Theorem. We also disc
uss the relationship between effective weak convergence and the structure
of the space of finite Borel measures on the real line as a computable met
ric space. In contrast to effective weak convergence\, we give an example
of an effectively vaguely convergent sequence of measures that has an inco
mputable limit. Nevertheless\, we discuss the conditions for which the lim
it of an effectively vaguely convergent sequence is computable and the con
ditions for which effective weak and vague convergence of measures coincid
e. This talk will feature joint work with Timothy McNicholl.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/65/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cristóbal Rojas (Pontifical Catholic University of Chile)
DTSTART:20211108T213000Z
DTEND:20211108T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/66
DESCRIPTION:Title: Computability of Harmonic Measure\nby Cristóbal Rojas (Pontifical
Catholic University of Chile) as part of Computability theory and applica
tions\n\n\nAbstract\nWe will review recent results relating the geometry o
f a connected domain to the computability of its harmonic measure at a giv
en point x. In particular\, we will discuss examples of domains whose harm
onic measure at x is always computable relative to x\, but not uniformly.
As a by-product\, this construction produces "natural" examples of harmoni
c functions arising as solutions to a Dirichlet problem which are piecewis
e computable (i.e. all their values are computable relative to the input p
oint)\, but not computable. This is a work in collaboration with I. Binder
\, A. Glucksam and M. Yampolsky.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/66/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Elvira Mayordomo (University of Zaragoza)
DTSTART:20211122T213000Z
DTEND:20211122T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/67
DESCRIPTION:Title: Extending the reach of the point-to-set principle\nby Elvira Mayor
domo (University of Zaragoza) as part of Computability theory and applicat
ions\n\n\nAbstract\nThe point-to-set principle of J. Lutz and N. Lutz (201
8) has\nrecently enabled the theory of computing to be used to answer open
questions\nabout fractal geometry in Euclidean spaces R^n. These are clas
sical questions\nwhose statements do not involve computation or related as
pects of logic.\n\nI will present the generalization of the point-to-set p
rinciple from Euclidean\nspaces to arbitrary separable metric spaces and t
o a large class of gauge\nfamilies.\n\nThen I will demonstrate the power o
f our extended point-to-set principle by\nusing it to prove new theorems a
bout classical fractal dimensions in\nhyperspaces.\n\n(The results present
ed are joint work with Jack Lutz and Neil Lutz).\n
LOCATION:https://stable.researchseminars.org/talk/CTA/67/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Francesca Zaffora Blando (Carnegie Mellon University)
DTSTART:20211206T213000Z
DTEND:20211206T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/68
DESCRIPTION:Title: Algorithmic randomness and Bayesian convergence\nby Francesca Zaff
ora Blando (Carnegie Mellon University) as part of Computability theory an
d applications\n\n\nAbstract\nMuch recent work in algorithmic randomness h
as concerned\ncharacterizations of randomness notions in terms of effectiv
izations of\nalmost-everywhere convergence theorems in analysis and probab
ility theory. In\nthis talk\, I will consider some results that are part o
f the basic toolkit of\nBayesian epistemologists from this perspective. In
particular\, I will focus on\ncertain martingale convergence theorems tha
t form one of the cornerstones of\nBayesian epistemology and that fall und
er the general umbrella of "Bayesian\nconvergence-to-the-truth results". T
hese results are standardly taken to\nestablish that a Bayesian agent’s
beliefs are guaranteed to converge to the\ntruth with probability one as t
he evidence accumulates. We will see that\, for\ncomputable Bayesian agent
s (i.e.\, Bayesian agents with computable priors)\, we\nnot only have that
convergence to the truth occurs with probability one\, but\nwe can also p
rovide precise characterizations of the data streams along which\nbeliefs
converge to the truth: they are precisely the algorithmically random\ndata
streams. I will conclude by sketching a broader computability-theoretic\n
approach to Bayesian epistemology suggested by these results.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/68/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Takayuki Kihara (Nagoya University)
DTSTART:20211005T130000Z
DTEND:20211005T140000Z
DTSTAMP:20260404T094532Z
UID:CTA/69
DESCRIPTION:Title: Lawvere-Tierney topologies for computability theorists\nby Takayuk
i Kihara (Nagoya University) as part of Computability theory and applicati
ons\n\n\nAbstract\nIn this talk\, we study the frame of Lawvere-Tierney to
pologies on Hyland's effective topos. For this purpose\, we introduce a ne
w computability-theoretic reducibility notion\, which is a common extensio
n of the notions of Turing reducibility and generalized Weihrauch reducibi
lity. Based on the work by Lee and van Oosten\, we utilize this reducibili
ty notion for providing a concrete description of the frame of the Lawvere
-Tierney topologies on the effective topos. As an application\, we solve s
everal open problems proposed by Lee and van Oosten. For instance\, we sho
w that there exists no minimal Lawvere-Tierney topology which is strictly
above the identity topology on the effective topos.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/69/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dino Rossegger (UC Berkeley)
DTSTART:20211102T200000Z
DTEND:20211102T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/70
DESCRIPTION:Title: New examples of degrees of categoricity\nby Dino Rossegger (UC Ber
keley) 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 degr
ee with $\\mathbf 0^{(\\alpha)}\\leq \\mathbf d\\leq \\mathbf 0^{(\\alpha+
1)}$ for some computable $\\alpha$\, then $\\mathbf d$ is a degree of cate
goricity. For $\\alpha\\geq 2$ we modify a technique developed by Dan Ture
tsky to code paths through trees into the automorphisms of structures. Thi
s allows us to obtain structures with these degrees of categoricity that a
re rigid and have computable dimension $2$. For both properties\, this is
the least $\\alpha$ where we can obtain this result. Goncharov showed that
if a structure is $\\mathbf 0'$-computably categorical\, then it can not
have finite computable dimension other than $1$. Bazhenov and Yamaleev con
structed a properly d-c.e.\\ degree $\\mathbf d$\, that is not the degree
of categoricity of a rigid structure. We combine their construction with t
rue stages to obtain a degree $\\mathbf d$\, $\\mathbf 0'<\\mathbf d< \\ma
thbf 0''$ that is not the degree of categoricity of a rigid structure. Thi
s is joint work with Barbara Csima.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/70/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Karen Seidel (Hasso Plattner Institute\, University of Potsdam)
DTSTART:20211130T200000Z
DTEND:20211130T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/71
DESCRIPTION:Title: Modelling binary classification\nby Karen Seidel (Hasso Plattner I
nstitute\, University of Potsdam) as part of Computability theory and appl
ications\n\n\nAbstract\nIn machine learning\, algorithms generalise from a
vailable training data to unseen situations.\nThe engineering practices us
ed in the respective technologies are far from understood.\nResearch in \\
emph{inductive inference} analyses concrete mathematical models for this c
omplex subject with tools from computability theory.\n\nWe investigate mod
els for incremental binary classification\, an example for supervised onli
ne learning.\nOur starting point is a model for human and machine learning
suggested by E.~M.~Gold.\n\nFor learning algorithms that use all of the a
vailable binary labeled training data in order to compute the current hypo
thesis\, we observe that the distribution of the training data does not in
fluence learnability.\nWhen approximating the concept to be learned\, we o
btain a strict hierarchy\, depending on the error parameter.\nWe consider
different hypothesis spaces for spam problem like and symmetric classifica
tion tasks and provide the complete maps.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/71/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Donald Stull (Northwestern University)
DTSTART:20220124T213000Z
DTEND:20220124T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/72
DESCRIPTION:Title: The dimension spectrum conjecture for lines\nby Donald Stull (Nort
hwestern University) as part of Computability theory and applications\n\n\
nAbstract\nEffective dimension gives a fine-grained measure of randomness
of individual 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 individual points on L. Jack Lutz\, in the early 2000s\, posed the dim
ension spectrum conjecture. This conjecture states that\, for every line L
\, sp(L) contains a unit interval. In this talk\, we present a proof of th
e dimension spectrum conjecture. We also discuss its relation to open prob
lems in geometric measure theory\, and avenues for future research.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/72/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Harrison-Trainor (University of Michigan)
DTSTART:20220207T213000Z
DTEND:20220207T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/73
DESCRIPTION:Title: Kolmogorov extractors and evenly-distributed hypergraphs\nby Matth
ew Harrison-Trainor (University of Michigan) as part of Computability theo
ry and applications\n\n\nAbstract\nSuppose that we have a string which has
some amount of randomness\nand we want to produce from it\, in an effecti
ve way\, a string which is more\nrandom. Though we cannot do this\, it is
possible to produce two strings\, at\nleast one of which is more random th
an the original string. Moreover\, the more\nstrings we are allowed to pro
duce\, the more we can increase the randomness.\nHow much can we increase
the randomness\, and how many strings are required?\nThis question turns o
ut to be related to a purely graph-theoretic question\nabout how evenly th
e edges of a hypergraph can be distributed.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/73/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ekaterina Fokina (Vienna University of Technology)
DTSTART:20220221T213000Z
DTEND:20220221T223000Z
DTSTAMP:20260404T094532Z
UID:CTA/74
DESCRIPTION:Title: Algorithmic learning of structures\nby Ekaterina Fokina (Vienna Un
iversity of Technology) as part of Computability theory and applications\n
\n\nAbstract\nAssume we have a class of structures closed under isomorphis
m.\nAssume further\, we receive information about one of these structures
step by\nstep: finitely much information at each step. Our goal is to dete
rmine\, after\nfinitely many steps\, which structure from the class we are
observing. If we\ncan reach the goal\, we call the class learnable. In th
e talk we formalise\nvarious aspects of this problem using ideas from comp
utable structure theory\nand computational learning theory. We give syntac
tic characterisations for\nseveral notions of learnability and apply these
results to get examples of\nlearnable and non-learnable classes of struct
ures.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/74/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Emmanuel Rauzy (Université de Paris)
DTSTART:20220201T160000Z
DTEND:20220201T170000Z
DTSTAMP:20260404T094532Z
UID:CTA/75
DESCRIPTION:Title: Computable analysis on the space of marked groups\nby Emmanuel Rau
zy (Université de Paris) as part of Computability theory and applications
\n\n\nAbstract\nI will present some results that concern the study of Mark
ovian computable analysis on the topological space of marked groups. While
this work was originally motivated by questions in group theory\, it turn
ed out to be also very interesting from the point of view of computable an
alysis alone\, providing the first naturally arising Polish space that is
not effectively Polish.\nIndeed\, while it is effectively complete and sep
arable\, the space of marked groups is not effectively separable: any sequ
ence that is dense in it is non-computable. I will also present a phenomen
on of failure of an effective axiom of choice: there is no algorithm that
can\, given a non-empty basic clopen set\, produce a group that belongs to
this set. Because of this\, none of the well known results of Kreisel-Lac
ombe-Schoenfield\, Ceitin and Moschovakis\, and that establish the effecti
ve continuity of computable functions in different settings\, can be appli
ed to the space of marked groups.\nMy talk will focus on presenting some c
lassical theorems of the theory of decision problems for groups (Boone-Nov
ikov\, Boone-Rogers\, etc)\, in order to show how those theorems apply to
the space of marked groups.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/75/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yue Yang (National University of Singapore)
DTSTART:20220215T010000Z
DTEND:20220215T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/76
DESCRIPTION:Title: Strong minimal pair problem\nby Yue Yang (National University of S
ingapore) as part of Computability theory and applications\n\n\nAbstract\n
This talk is about recursively enumerable (r.e.) Turing degrees. We say th
at two nonzero r.e. degrees a and b form a strong minimal pair\, if a ∧
b = 0 and for any nonzero r.e. degree x ≤ a\, b ∨ x ≥ a. Joint with
Mingzhong Cai\, Yiqun Liu\, Yong Liu\, and Cheng Peng\, we are able to sho
w the nonexistence of such a pair. I will not make any attempt to outline
the proof. Instead\, I plan to talk about our result in relation to earlie
r ones in the literature\, and mention a few interesting (or strange) feat
ures of the construction. For instance\, the construction is highly nonuni
form\, we have to prepare three different (families of) sets and one of th
em 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 audie
nces.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/76/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tin Lok Wong (National University of Singapore)
DTSTART:20211215T090000Z
DTEND:20211215T100000Z
DTSTAMP:20260404T094532Z
UID:CTA/77
DESCRIPTION:Title: Arithmetic under negated induction\nby Tin Lok Wong (National Univ
ersity of Singapore) as part of Computability theory and applications\n\n\
nAbstract\nArithmetic generally does not admit any non-trivial quantifier
elimination. I will talk about one exception\, where the negation of an in
duction axiom is included in the theory. Here the Weak Koenig Lemma from r
everse mathematics arises as a model completion.This work is joint with Ma
rta Fiori-Carones (Novosibirsk)\, Leszek Aleksander Kolodziejczyk (Warsaw)
and Keita Yokoyama (Sendai).\n
LOCATION:https://stable.researchseminars.org/talk/CTA/77/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew de Brecht (Kyoto University)
DTSTART:20220111T120000Z
DTEND:20220111T130000Z
DTSTAMP:20260404T094532Z
UID:CTA/79
DESCRIPTION:Title: The category of quasi-Polish spaces as a represented space\nby Mat
thew de Brecht (Kyoto University) as part of Computability theory and appl
ications\n\n\nAbstract\nQuasi-Polish spaces are a class of well-behaved co
untably based spaces which include Polish spaces\, omega-continuous domain
s\, and countably based spectral spaces. In this talk\, we will show how t
o construct the category of quasi-Polish spaces as a represented space\, a
nd demonstrate the computability of some standard category-theoretical con
structions such as products and equalizers. As an example of some less tri
vial constructions\, we use domain theoretic techniques to verify the comp
utability of various powerspace functors on the category of quasi-Polish s
paces. (This work was supported by JSPS KAKENHI Grant Number 18K11166).\n
LOCATION:https://stable.researchseminars.org/talk/CTA/79/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Peter Cholak (University of Notre-Dame)
DTSTART:20220301T200000Z
DTEND:20220301T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/80
DESCRIPTION:Title: Old and new results on the computably enumerable sets\nby Peter Ch
olak (University of Notre-Dame) as part of Computability theory and applic
ations\n\n\nAbstract\nWe will survey a number of old results on the comput
ably enumerable sets and finish with a few new results. The computably en
umerable sets are interesting since anything which can happen computably h
appens in computably enumerable sets.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/80/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rupert Hölzl (UniBw Munich)
DTSTART:20220316T130000Z
DTEND:20220316T140000Z
DTSTAMP:20260404T094532Z
UID:CTA/81
DESCRIPTION:Title: Rank and Randomness (Cancelled)\nby Rupert Hölzl (UniBw Munich) a
s part of Computability theory and applications\n\n\nAbstract\nThis talk h
as been cancelled and will be moved to a later date.\n\nWe show that for e
ach computable ordinal $\\alpha>\;0$ it is possible to find in\neach Mar
tin-Löf random $\\Delta^0_2$ degree a sequence $R$ of Cantor-Bendixson\nr
ank $\\alpha$\, while ensuring that the sequences that inductively witness
$R$'s\nrank are all Martin-Löf random with respect to a single countably
supported\nand computable measure. This is a strengthening for random deg
rees of a recent\nresult of Downey\, Wu\, and Yang\, and can be understood
as a randomized version\nof it. (Joint result with Christopher P. Porter.
)\n
LOCATION:https://stable.researchseminars.org/talk/CTA/81/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Valentina Harizanov (George Washington University)
DTSTART:20220330T000000Z
DTEND:20220330T010000Z
DTSTAMP:20260404T094532Z
UID:CTA/82
DESCRIPTION:Title: Computable isomorphism problem\nby Valentina Harizanov (George Was
hington University) as part of Computability theory and applications\n\n\n
Abstract\nThese classes include arbitrary structures with at least one rel
ation of arity at least $2$\, abelian $p$-groups\, linear orders\, Boolean
algebras\, fields of a fixed characteristic\, nilpotent semigroups\, nilp
otent groups\, and nilpotent rings. These classes have isomorphic computab
le structures that are not hyperarithmetically isomorphic. One of the meth
ods we use to establish $\\Sigma _{1}^{1}$-completeness of the isomorphism
problem for $K$ is based on a uniform effective interpretation\nof comput
able structures in a specific class into computable structures in $K$.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/82/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Meng Che "Turbo" Ho (California State University Northridge)
DTSTART:20220321T203000Z
DTEND:20220321T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/83
DESCRIPTION:Title: Zero-one laws for finitely presented structures\nby Meng Che "Turb
o" Ho (California State University Northridge) as part of Computability th
eory and applications\n\n\nAbstract\nGromov proposed the notion of random
groups as a model to study the typical behavior of finitely presented grou
ps. They share many properties of the free group\, and Knight conjectured
that random 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\, w
e consider random presentations in algebraic varieties in the sense of uni
versal algebra. We will discuss some examples where the zero-one law holds
and some other examples where the zero-one law fails. We also establish s
ome general conditions for the zero-one law to hold (or fail).\n
LOCATION:https://stable.researchseminars.org/talk/CTA/83/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jun Le Goh (University of Wisconsin)
DTSTART:20220404T203000Z
DTEND:20220404T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/84
DESCRIPTION:Title: Extensions of embeddings in the $\\Sigma^0_2$ enumeration degrees\
nby Jun Le Goh (University of Wisconsin) as part of Computability theory a
nd applications\n\n\nAbstract\nIn order to \nmeasure the \nalgorithmic con
tent of partial functions\, or the positive information \ncontent of subse
ts of the natural numbers\, one can use the notion of \nenumeration reduci
bility. The associated degree structure\, known as the \nenumeration degre
es (e-degrees)\, forms a superstructure of the Turing \ndegrees. We presen
t ongoing work with Steffen Lempp\, Keng Meng Ng and \nMariya Soskova on t
he algebraic properties of a countable substructure of \nthe e-degrees\, n
amely the &Sigma\;02
e-degrees.\n
\n\nThe &Sigma\;02 \ne-degrees are analogous to the \ncomputably enumerable
(c.e.) \nTuring degrees but these structures are not elementarily equival
ent as \npartial orders. Indeed\, Ahmad showed that there are incomparable
\n&Sigma\;02\ne-degre
es a and b such that if c < a\, then \nc < b\, implying that a cannot \nbe expressed as the join of
two degrees below it. This stands in contrast \nto Sacks's splitting theo
rem for the c.e. Turing degrees.\n
\n\nOne can view Ahmad's result
as a two-quantifier sentence in the language \nof partial orders which hol
ds in the &Sigma\;02
\ne-degrees. While it is easy \nto compute whether a given one-quantifier
sentence is true in the \n&Sigma\;02 \ne-degrees (because all finite partial orders embed)\, th
e \ncorresponding task for two-quantifier sentences (which corresponds to
an \nextension of embeddings problem) is not known to be algorithmically \
ndecidable. Towards solving this problem\, we investigate the extent to \n
which Ahmad's result can be generalized. For instance\, we show that it \n
does not generalize to triples: For any incomparable \n&Sigma\;02 e-degrees \na\, b and c\, there is some x such that one of \nthe following h
olds: x is \nbelow a but not below b\, or x is
below b but \nnot below c.\n
\n\nWe shall also discu
ss speculative generalizations of the above result\, and \nhow they may le
ad to an algorithm which decides a class of two-quantifier \nsentences in
the &Sigma\;02 e-deg
rees.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/84/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Melnikov (Victoria University of Wellington)
DTSTART:20220412T010000Z
DTEND:20220412T020000Z
DTSTAMP:20260404T094532Z
UID:CTA/85
DESCRIPTION:Title: Primitive recursive mathematics\nby Alexander Melnikov (Victoria U
niversity of Wellington) as part of Computability theory and applications\
n\n\nAbstract\nWe discuss the recently revived approach to computable\nmat
hematics via primitive recursion. This theory aims to\neliminate the use o
f unbounded search from \ncomputable structure theory\, computable analysi
s\, etc.\nWe will be focused on the recent developments in the theory\,\nb
ut we begin with an overview of what is known so far.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/85/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeff Hirst (Appalachian State University)
DTSTART:20220418T203000Z
DTEND:20220418T213000Z
DTSTAMP:20260404T094532Z
UID:CTA/86
DESCRIPTION:Title: Three views of LPO and LLPO\nby Jeff Hirst (Appalachian State Univ
ersity) as part of Computability theory and applications\n\n\nAbstract\nTh
e Limited Principle of Omniscience (LPO) and Lesser Limited\nPrinciple of
Omniscience (LLPO) are frequently included in discussions of\nconstructive
mathematics. We will compare and contrast the principles using\nideas fr
om Weihrauch reducibility\, reverse mathematics\, and higher order\nrevers
e mathematics. The preliminary results in higher order reverse\nmathemati
cs are joint work with Carl Mummert.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/86/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefan Vatev (University of Sofia "St. Kliment Ohridski")
DTSTART:20220427T080000Z
DTEND:20220427T090000Z
DTSTAMP:20260404T094532Z
UID:CTA/87
DESCRIPTION:Title: Effective embeddings for classes of structures via enumeration operato
rs\nby Stefan Vatev (University of Sofia "St. Kliment Ohridski") as pa
rt of Computability theory and applications\n\n\nAbstract\nOne can effecti
vize the notion of Borel embedding for classes of structures by considerin
g Turing 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 embedding relate to each other \neven if we consider some simple cla
sses of structures such as pairs of linear orderings\, closed under isomor
phism.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/87/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Clara Löh (University Regensburg)
DTSTART:20221128T130000Z
DTEND:20221128T140000Z
DTSTAMP:20260404T094532Z
UID:CTA/88
DESCRIPTION:Title: $L^2$-Betti numbers and computability of reals\nby Clara Löh (Uni
versity Regensburg) as part of Computability theory and applications\n\n\n
Abstract\nFor several real-valued invariants from topology or group theory
\, the individual values are not arbitray real numbers\, but (right-)compu
table reals. For example\, the real numbers arising as $L^2$-Betti numbers
of groups are right-computable\, where the right-computability degree is
bounded by the Turing degree of the word problem. \n\nI will give an overv
iew of such results on $L^2$-Betti numbers and related invariants. This ta
lk is based on joint work with Matthias Uschold.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/88/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Linus Richter (Victoria University Wellington)
DTSTART:20230130T200000Z
DTEND:20230130T210000Z
DTSTAMP:20260404T094532Z
UID:CTA/89
DESCRIPTION:Title: Co-analytic Counterexamples to Marstrand’s Projection Theorem\nb
y 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 subse
t of Euclidean space in terms of the complexity of its individual points.
“Complexity" here refers to Kolmogorov complexity—so the point-to-set
principle gives us an algorithmic handle on classical problems in fractal
geometry: sets with particular fractal properties can now be constructed i
n stages\, point-by-point\, by coding “enough” information into each p
oint\, bit-by-bit.\nI will give a brief introduction to all these notions\
, and present a new result in fractal geometry whose proof uses such effec
tive methods: under V=L\, I will outline the construction of co-analytic c
ounterexamples to Marstrand’s Projection Theorem\, one of fractal geomet
ry’s seminal theorems about the dimension of orthogonal projections of a
nalytic plane sets onto lines. Our results also show that Marstrand’s th
eorem is indeed sharp for analytic sets\, a fact previously unknown.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/89/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Valentino Delle Rose (Centro Nacional de Inteligencia Artificial\,
Chile)
DTSTART:20230221T140000Z
DTEND:20230221T150000Z
DTSTAMP:20260404T094532Z
UID:CTA/90
DESCRIPTION:Title: Computable PAC learning\nby Valentino Delle Rose (Centro Nacional
de Inteligencia Artificial\, Chile) as part of Computability theory and ap
plications\n\n\nAbstract\nPAC (probably approximately correct) learning is
a framework for the theoretical analysis of machine learning\, proposed b
y Valiant in 1984. Intuitively\, we consider a certain class of hypotheses
: a learner for this class receives a finite amount of random samples of a
n unknown objective function and\, with high probability\, outputs a funct
ion which approximates the objective function no worse than any hypothesis
in the given class.\nThe fundamental theorem of statistical learning char
acterizes the existence of a learner for a certain class of hypotheses wit
h a combinatorial 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 consi
dered as functions\, without taking into account any effectiveness aspect:
what does it happen\, then\, when we only focus on learners which can be
implemented by some algorithmic procedure?\nTo investigate this question\,
Agarwal et al. (2020) introduced computable PAC (CPAC) learning\, where b
oth the learner and the functions it outputs are required to be computable
. Their key observation is that\, in this new framework\, the finiteness o
f VC dimension does no longer suffice to ensure the existence of a computa
ble learner. Moreover\, this computable setting is affected by certain asp
ects which do not make any difference in classical PAC learning: for examp
le\, whether the learner is required to be proper (i.e. its range must be
contained in the class of hypotheses to be learned) or allowed to be impro
per (i.e. it can output any function)\, or whether the number of samples t
he learner needs to actually learn the class is bounded by a computable fu
nction.\nBut which of these aspects actually lead to different versions of
computable learnability? In this talk\, we will provide a landscape of th
e field\, based on previous work of Agarwal et al. (2020)\, Sterkenburg (2
022) and recent joint work with Alexander Kozachinskiy\, Cristóbal Rojas
and Tomasz Steifer (Pontificia Universidad Católica de Chile).\n
LOCATION:https://stable.researchseminars.org/talk/CTA/90/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Juan Aguilera (Vienna University of Technology)
DTSTART:20230404T100000Z
DTEND:20230404T110000Z
DTSTAMP:20260404T094532Z
UID:CTA/91
DESCRIPTION:Title: Determinacy in Second-Order Arithmetic\nby Juan Aguilera (Vienna U
niversity of Technology) as part of Computability theory and applications\
n\n\nAbstract\nWe survey some recent results on the Reverse Mathematics of
determinacy principles in Second-Order Arithmetic.\n
LOCATION:https://stable.researchseminars.org/talk/CTA/91/
END:VEVENT
END:VCALENDAR