Семинар МЛ ТИ "Арифметики Бюхи и конечные автоматы"

Дата: 11 декабря 2026 г., 18:10 - 19:30

Докладчик: Запрягаев Александр, научный сотрудник, международная лаборатория теоретической информатики

Аннотация: Арифметики Бюхи BA_n (n>=2) - важный класс слабых арифметических теорий, предложенный Ю. Бюхи для характеризации множеств натуральных чисел, принимаемых конечными автоматами. Структура является автоматной в том и только в том случае, если она интерпретируема в BA_n для некоторого (всех) n. Эта связь делает арифметики Бюхи мощным инструментом для исследования задач об автоматности при помощи методов логики и теории моделей. При этом собственно логические аспекты теорий BA_n остаются слабо исследованными: так, до сих пор не опубликовано явных аксиоматизаций BA_n и не найдено расширение языка, в котором возможна элиминация кванторов.

В докладе будет дан обзор как классических результатов об арифметиках Бюхи, таких, как теорема Кобхэма-Семёнова о связи между определимостью множеств в BA_n при различных значениях n, так и новых, полученных автором, включая "автоматную теорему Тенненбаума":

Теорема (З.). Существует только одна автоматная модель BA_n - стандартная.

Заметим, что вычислимые нестандартные модели BA_n существуют (З., Ковалёв, TBP). Эти и иные результаты о нестандартных моделях BA_n будут представлены на докладе.

Место проведения:

Очно: Покровский бул., 11, ауд. уточняется

Онлайн: Zoom 

Идентификатор конференции: 890 7168 8640
Код доступа: 337243