#матлог #учёба #спецсеминар

18 февраля 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.

Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533

С. Л. Кузнецов (МИАН)

Эффективная неотделимость и её применения для теорий с неподвижными точками

Аннотация:
Техника эффективной неотделимости позволяет доказывать теоремы об алгоритмической неразрешимости и $\Sigma^0_1$-полноте логических теорий в ситуациях, когда прямое сведение известных задач, таких как задача останова машины Тьюринга, построить не получается. Будет рассказано об эффективной неотделимости, приведена новая пара эффективно неотделимых множеств — нетотальных контекстно-свободных грамматик и так называемых регулярно тотальных контекстно-свободных грамматик. Далее с помощью этой пары будет доказана $\Sigma_0^1$-полнота эквациональных теорий алгебр Клини с делениями и алгебр Хомского — идемпотентных полуколец с оператором взятия наименьшей неподвижной точки.

Доклад частично основан на недавней совместной работе автора с А. Дасом и А. Де.
Доклад планируется на два заседания семинара.

➰ ВК