Computability in Mathematics

Computability in Mathematics

In  1936 Alonzo Church and Alan Turing famously proposed two equivalent formal models of what it means for a function to be computable. This was an essential prerequisite to answer a question by Hilbert (the Entscheidungsproblem), which asked for an automated way to solve ``all of mathematics''. Originally seen as a theme of limited interest, the notion regained popularity with the advent of modern computers. Since then, algorithmic approaches to different problems in theoretical mathematics have become increasingly important.
    
    We will describe the basic notions of computability required to prove decidability and undecidability results in mathematics. Several models of computability (Turing-computability, $\mu$-recursivity) will be discussed in the course, as well as general tools and applications, for example the Halting-Problem, Turing reducability, Oracle-based computations,  the arithmetical hierarchy, and more.
    This will then allow us to discuss computability in the context of theoretical mathematics, f.e. in group theory, real analysis, logic, linear algebra.
    
    The course will be structured into two halves, the first consisting of introductory talks on the topic of general computability and the second consisting of talks given by the participants, concerning specific questions in the realm of computability and theoretical mathematics.
    A concrete list of suggestions for talks will be provided in the organization meeting, some ideas are: the Domino Problem, the Word and Conjugacy Problem in groups, the field of computable reals.
    There will be topics suitable for both MSc and BSc students, prior knowledge in computer science is not at all required. The seminar can be chosen both as a Seminar or Proseminar, respective passing modalities can be organized.

Topics

Each participant of the seminar will give a 90min talk. Here is a list of possible topics and resources for them. Here is the list of topics still available for talks, respective supervisors and (in due time) dates for the talks.

Modalities

Talks will be given in English and should last about 90min.

For the introductory part of the seminar, there will be exercise sheets, 4 in total. If you are taking the seminar as a full seminar (7 ECTS), you have to submit the sheets and reach at least 50% of the points, and at the end of the introductory part complete a small homework assignment that will be graded. If you are taking the seminar as a proseminar (5 ECTS), this is not necessary.

Exercise Sheets

The exercise sheets can be found here and should be submitted in mailbox no. 41 by their respective deadlines, also to be found in the timetable.