Курс посвящён классическим алгоритмическим вопросам алгебры, которые активно изучались, начиная с 1940-х годов, после того, как был сформулирован тезис Чёрча–Тьюринга, давший точное определение эффективно вычислимым функциям. Таким образом, стало возможным доказывать невозможность построения алгоритма для решения массовой проблемы. Содержание курса будут составлять последовательно излагаемые алгоритмические проблем алгебры, для большей части которых доказывается алгоритмическая неразрешимость. В частности, будут рассматриваться проблема равенства в полугруппах, проблема вырождения произведения матриц, проблемы равенства, сопряжённости и вхождения в группах, а также проблема изоморфизма групп. Также в курс войдут известные примеры разрешимых задач, такие как проблема проблема равенства в финитно аппроксимируемых группах и проблема вхождения для свободных групп. Для освоения курса желательно знать основы математической логики и теории алгоритмов, а также основы теории групп.
Финансовая поддержка. Курс проводится при финансовой поддержке Фонда Саймонса и Минобрнауки России (грант на создание и развитие МЦМУ МИАН, соглашение № 075-15-2019-1614).
RSS: Ближайшие семинары
Лектор
Таламбуца Алексей Леонидович
Организации
Математический институт им. В.А. Стеклова Российской академии наук, г. Москва Математический центр мирового уровня «Математический институт им. В.А. Стеклова Российской академии наук» (МЦМУ МИАН) |