Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 25131

Weihrauch Complexity: Structuring the Realm of Non-Computability

( Mar 23 – Mar 28, 2025 )

Please use the following short url to reference this page:




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.)
Copyright 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)

  • Logic in Computer Science

  • Computability and complexity
  • combinatorial problems
  • reverse and constructive mathematics
  • computable analysis
  • Weihrauch reducibility and related reducibilities