Dagstuhl-Seminar 25131
Weihrauch Complexity: Structuring the Realm of Non-Computability
( 23. Mar – 28. Mar, 2025 )
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/25131
Organisatoren
- Vasco Brattka (Universität der Bundeswehr - München, DE)
- Alberto Marcone (University of Udine, IT)
- Arno Pauly (Swansea University, GB)
- Linda Westrick (Pennsylvania State University - University Park, US)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
This Dagstuhl Seminar is dedicated to the investigation of two active areas of research, one in theoretical computer science, the other in mathematical logic. These are computable analysis on the one hand, and reverse mathematics and applied computability theory on the other. That there is a deep connection between these areas was first suggested by Gherardi and Marcone (2008) and later independently by Dorais, Dzhafarov, Hirst, Mileti, and Shafer (2016) and Hirschfeldt and Jockusch (2016). The past decade has seen this connection blossom into a rich and productive area of research, with by now many papers and several PhD theses dedicated to it. Results in this area fall into two intertwined groups: Some clarify the structure of the degrees of non-computability; some further our understanding of the precise nature of non-computability of particular computational tasks of interest. Grasping the nature of non-computability is a profound goal mirroring the quest to understand the nature of computation. Knowing the degree of non-computability of a computational task brings with it answers as to whether weaker or approximate versions of it might be solvable. This interdisciplinary development was fostered not least by the two precursor Dagstuhl Seminars on this topic. The current seminar will explore recent trends and results, open questions, and new directions of this fascinating field of research that has become known as Weihrauch complexity. These include:
- New interior and closure operators (first-order part of problems, deterministic part of problems etc.)
- Game-theoretic classifications and dichotomies in the Weihrauch lattice
- Analogous of induction and boundedness principles and the Paris-Harrington hierarchy
- New choice principles in the Weihrauch lattice (overt, analytic choice etc.)
- Relations to new categorical and logical approaches (Lawvere-Tierney topologies, instancewise versions of Weihrauch reducibility)
- Global structure of the Weihrauch lattice (chains, antichains, density, etc.)
Creative Commons BY 4.0
Vasco Brattka, Alberto Marcone, Arno Pauly, and Linda Westrick
Verwandte Seminare
- Dagstuhl-Seminar 15392: Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis (2015-09-20 - 2015-09-25) (Details)
- Dagstuhl-Seminar 18361: Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis (2018-09-02 - 2018-09-07) (Details)
Klassifikation
- Logic in Computer Science
Schlagworte
- Computability and complexity
- combinatorial problems
- reverse and constructive mathematics
- computable analysis
- Weihrauch reducibility and related reducibilities
