Алгоритмические вопросы алгебры

Курс посвящён классическим алгоритмическим вопросам алгебры, которые активно изучались, начиная с 1940-х годов, после того, как был сформулирован тезис Чёрча–Тьюринга, давший точное определение эффективно вычислимым функциям. Таким образом, стало возможным доказывать невозможность построения алгоритма для решения массовой проблемы. Содержание курса будут составлять последовательно излагаемые алгоритмические проблем алгебры, для большей части которых доказывается алгоритмическая неразрешимость. В частности, будут рассматриваться проблема равенства в полугруппах, проблема вырождения произведения матриц, проблемы равенства, сопряжённости и вхождения в группах, а также проблема изоморфизма групп. Также в курс войдут известные примеры разрешимых задач, такие как проблема проблема равенства в финитно аппроксимируемых группах и проблема вхождения для свободных групп. Для освоения курса желательно знать основы математической логики и теории алгоритмов, а также основы теории групп.