The course is devoted to classical decision problems in algebra, which have been actively studied since the 1940s, after the Church–Turing thesis was formulated, which gave a precise definition of effectively computable functions. Thus, it became possible to prove the inexistence of an algorithm for a certain problem defined for infinitely many inputs. The course will cover a number of decision problems in algebra, for most of which algorithmic undecidability will be proved. In particular, we will consider the word problem in semigroups, the mortality problem for matrices, the generalized word and conjugacy problems in groups, and the isomorphism problem for groups. Also, the course will include well-known examples of decidable problems, such as the word problem in residually finite groups and the generalized word problem in free groups. To master the course, it is desirable to be familiar with basics of mathematical logic and group theory.

Financial support. The course is supported by the Simons Foundation and the Ministry of Science and Higher Education of the Russian Federation (the grant to the Steklov International Mathematical Center, Agreement no. 075-15-2019-1614).

Lecturer
Talambutsa Alexey Leonidovich

Institutions
Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
Steklov International Mathematical Center