Dagstuhl Seminar 25131
Weihrauch Complexity: Structuring the Realm of Non-Computability
( Mar 23 – Mar 28, 2025 )
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25131
Organizers
- 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)
Contact
- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
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
Related Seminars
- 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)
Classification
- Logic in Computer Science
Keywords
- Computability and complexity
- combinatorial problems
- reverse and constructive mathematics
- computable analysis
- Weihrauch reducibility and related reducibilities
