New Directions in Computability Theory
Nouvelles directions en calculabilité
7 – 11 March 2022
|
Scientific Committee
Comité scientifique Peter Cholak (University of Notre Dame) |
Organizing Committee
Comité d’organisation Denis Hirschfeldt (University of Chicago) |
|
Computability theory is one of the main branches of mathematical logic. It explores the computational content of mathematics. This theory was born in the beginning of the 20th century, as a way to answer the philosophical question of how to formally characterize the functions one can “compute”,in an intuitive sense. Since then, the field has seen considerable progress and development, leading to what is today a very rich theory on the computational strength and content of various mathematical objects. It has also been successfully applied to other areas of mathematics, giving rise to several subfields within which most of today’s research is concentrated. This conference aims to encompass the various applications of computability theory, with a particular emphasis on recent developments and new research directions. We give here a non-exhaustive list of such subfields:
Algorithmic randomness: The study of randomness for individual objects such as reals. Reverse mathematics: The search for optimal axioms to prove mathematical theorems. Reducibility and degree structures: The study of the Turing degrees, and more generally ofvarious notions of comparison of computability-theoretic strength. Computable model theory: The study of computational aspects of mathematical structures. Higher computability: The study of other, more powerful models of computation. |
La théorie de la calculabilité est une des branches principales de la logique. Elle explore le contenu calculatoire des mathématiques. Cette théorie est née au début du XXème siècle, afin de répondre à laquestion philosophique de la caractérisation formelle des fonctions que l’on pouvait ”calculer” dans un sens intuitif. Depuis, ce domaine de recherche a connu un développement et des progrès considérables, menant à ce qui est aujourd’hui une théorie très riche sur le contenu et la force calculatoire d’objets mathématiques variés. La calculabilité a aussi été appliqué avec succès à d’autres domaines des mathématiques, donnant naissance à plusieurs sous-domaines, au sein desquels se concentre une grande partie de la recherche actuelle. Cette conférence porte sur les différentes applications de la calculabilité, en mettant l’accent sur les développements récents, ainsi que sur les futures directions de recherche, que nous classons ici en cinq thèmes :
L’aléatoire algorithmique : l’étude de l’aléatoire pour les objets mathématique, essentiellementles réels. Les mathématiques à rebours : la recherche des axiomes optimaux pour prouver les théorèmes mathématiques. Les réductions et degrés : L’étude des degrés Turing, et plus généralement d’autres notions de degrés, correspondant à d’autres manières de comparer la puissance calculatoire des réels. La théorie des modèles calculables : L’ ́étude des aspects calculatoires des structures mathématiques. Les calculabilités d’ordre supérieur : l’étude d’autres modèles de calcul, plus puissant que le modèle standard. |
Nikolai Bazhenov (Russian Academy of Sciences) Equivalence relations on reals, and learning for algebraic structures
Laurent Bienvenu (CNRS, Université de Bordeaux) Two more applications of the fireworks technique
Damir Dzhafarov (University of Connecticut) Some questions and observations about the structure of the Weihrauch degrees
Ekaterina Fokina (Vienna University of Technology) Bi-embeddability relation on computable structures
Jun Le Goh (University of Wisconsin-Madison) Pi^0_1 classes relative to an enumeration oracle
Noam Greenberg (Victoria University of Wellington) The reverse mathematics of Cousin’s lemma
Matthew Harrison Trainor (Victoria University of Wellington) Coding in structures
Iskander Kalimullin (Kazan Federal University) Punctual structures relative to oracles
Dariusz Kalociński (Institute of Computer Science) Degree spectra of computable functions on an answer to Wright’s question
Lu Liu (Central South University) Subclass of effective martingales: completeness phenomenon
Elvira Mayordomo (Iowa State University, IA) Effective dimensions and the point to set principle for separable spaces: the Hilbert cube and the hyperspace
Joseph Miller (University of Wisconsin-Madison) Introenumerable sets and the cototal enumeration degrees
Russell Miller (Queens College, City University of New York) Countable reductions, Borel equivalence relations, and computable structure theory
Keng Meng Ng (Nanyang Technological University) Planar graph colouring
André Nies (University of Auckland) Random sequences of quantum bits
Arno Pauly (Swansea University) The first-order and the deterministic part of Weihrauch degree
Theodore Slaman (University of California, Berkeley) Aspects of Hausdorff Dimension
Mariya Soskova (University of Wisconsin-Madison) One point extensions of antichains in the local structure of the enumeration degrees
Dan Turetsky (Victoria University of Wellington) Highness classes and coding
Linda Brown Westrick (Penn State University) Reverse math of Borel combinatorics
Liang Yu (Nanjing University) Some consequences of TD and sTD
 |
 |