Seminar: Das Wortproblem/The Word Problem

Inhaltsangabe / Literatur / empfohlene Vorkenntnisse Ein grundlegendes mathematisches Problem ist, welche Fragen algorithmisch beantwortet werden können bzw. welche Objekte überhaupt algorithmisch klassifiziert werden können. Ausgehend von Turings Entdeckung, dass das sogenannte Halteproblem nicht algorithmisch gelöst werden kann, kann man zeigen, dass selbst die einfachsten gruppentheoretischen Probleme nicht algorithmisch gelöst werden können. Ein solches Problem ist das Wortproblem: Gegeben sei eine Beschreibung einer Gruppe durch (endlich viele) Erzeuger und Relationen. Gibt es einen Algorithmus, der für Wörter in den Erzeugern entscheidet, ob das entsprechende Gruppenelement trivial ist oder nicht? Diese algorithmische Unzugänglichkeit der Gruppentheorie hat weitreichende Konsequenzen für viele mathematische Teilgebiete. Zum Beispiel folgt daraus, dass das Homöomorphieproblem für Mannigfaltigkeiten nicht algorithmisch lösbar ist. Insbesondere können Mannigfaltigkeiten nicht algorithmisch klassifiziert werden. In diesem Seminar werden wir die Grundlagen der (Un)Entscheidbarkeit kennenlernen und auf gruppentheoretische Probleme anwenden. Insbesondere werden wir sehen, dass es Gruppen mit algorithmisch unentscheidbarem Wortproblem gibt und die Konsequenzen für topologische Klassifikationsprobleme betrachten.

Content / Literature / Recommended previous knowledge It is a fundamental mathematical problem to determine which questions can be algorithmically answered and which types of objects admit an algorithmic classification at all. Turing's discovery of the algorithmic unsolvability of the so-called halting problem can be used to show that even the simplest group-theoretic problems possess no algorithmic solution. An example of such a problem is the word problem: Given a description of a group in terms of (finitely many) generators and relations, is there an algorithm that decides whether words in these generators represent the trivial group element or not? This algorithmic inaccessibility of group theory has far-reaching consequences for many fields in mathematics. For example, it follows that the homeomorphism problem for manifolds cannot be solved algorithmically. In particular, there is no algorithmic classification of manifolds. In this seminar, we will learn the foundations of (un)decidability and apply those to group-theoretic problems. In particular, we will see that there exist groups with unsolvable word problem and we will study the consequences for topological clasification problems.