# Computability in Mathematics Leon Pernak, Emmanuel Rauzy

24.01.2023

## 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.

### Organizational Meeting

We will have an organizational meeting on 09/02/2023 at 12am in SR9 (Building E2.4, room 319), where we will discuss topics, possible time slots and any other open questions. If you cannot participate or have other questions ahead of time, write us an e-mail.