February 19 – 24 , 2017, Dagstuhl Seminar 17081

Computability Theory


Klaus Ambos-Spies (Universität Heidelberg, DE)
Vasco Brattka (Universität der Bundeswehr – München, DE)
Rodney Downey (Victoria University – Wellington, NZ)
Steffen Lempp (University of Wisconsin – Madison, US)

For support, please contact

Dagstuhl Service Team


List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]


Computability is one of the fundamental notions of mathematics and computer science, trying to capture the effective content of mathematics and ist applications. Computability Theory explores the frontiers and limits of effectiveness and algorithmic methods. It has its origins in Gödel's Incompleteness Theorems and the formalization of computability by Turing and others, which later led to the emergence of computer science as we know it today. Computability Theory is strongly connected to other areas of mathematics and theoretical computer science. The core of this theory is the analysis of relative computability and the induced degrees of unsolvability; its applications are mainly to Kolmogorov complexity and randomness as well as mathematical logic, analysis and algebra. Current research in computability theory stresses these applications and focuses on algorithmic randomness, computable analysis, computable model theory, and reverse mathematics (proof theory). Recent advances in these research directions have revealed some deep interactions not only among these areas but also with the core parts of computability theory. The goal of this Dagstuhl Seminar is to bring together researchers from all parts of computability theory and related areas in order to discuss advances in the individual areas and the interactions among those.

  Creative Commons BY 3.0 DE
  Klaus Ambos-Spies and Rodney Downey


  • Data Structures / Algorithms / Complexity


  • Computability theory
  • Generic case complexity
  • Computable analysis
  • Computable algebra
  • Proof mining
  • Algorithmic randomness

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.