Доклад Александра Запрягаева на научно-исследовательском семинаре "Современные проблемы математики"

6 ноября стажер-исследователь МЛ ЛогЛинФФ Александр Запрягаев выступил с докладом "Арифметика Бюхи и теорема Кобхэма-Семёнова" в рамках научно-исследовательского семинара "Современные проблемы математической логики" Факультета математики НИУ ВШЭ.

А.А. Запрягаев

"Арифметика Бюхи и теорема Кобхэма-Семёнова"

Аннотация доклада:
В ходе доклада речь идет о представлении множеств, распознаваемых конечными автоматами, формулами в слабых арифметических теориях. Показано, что распознаваемость подмножества N^m чисел, записанных в k-ичной системе счисления, автоматом эквивалентна выразимости с помощью сложения и дополнительной функции "y - наибольшая степень k, на которую делится x". Тем самым, существует серия расширений арифметики Пресбургера (теории натуральных чисел со сложением), естественно соответствующая автоматным подмножествам натурального ряда.
Обсуждались связанные вопросы алгоритмической разрешимости. Также было намечено доказательство фундаментальной теоремы Кобхэма-Семёнова, которая связывает определимость при различных основаниях систем счисления k1, k2: если показатели k1 и k2 мультипликативно независимы (т.е. не существует s, t > 0, r > 1 таких, что r^s = k1, r^t = k2), то определимость подмножества N^m независимо в арифметиках Бюхи с показателем k1 и k2 эквивалентна простой определимости в арифметике Пресбургера.

Видеозапись доклада