Семинар Добрушинской математической лаборатории. 28 ноября, вторник, 16:00, ауд. 307.
Александр Шень (ИППИ): Нормальные последовательности и автоматная сложность.
Аннотация: Хорошо известно, что нормальные последовательности (те, где любая группа цифр встречается с одинаковой предельной частотой) можно описать как несжимаемые с помощью конечных автоматов. Однако стандартная формулировка критерия такого рода (Becher, Heiber, 2014) не соответствует общей схеме определения несжимаемости в терминах колмогоровской сложности. Этот критерий можно переформулировать, введя понятие автоматной сложности, и тогда классические результаты о нормальных последовательности (сохранение нормальности двоичного числа при умножении на рациональное, эквивалентность разных определений, а также теорема Пятецкого-Шапиро о нормальности последовательности, в которой частоты появления всех блоков не более чем в константу раз превосходят ожидаемые) получают простые и естественные доказательства в терминах конечных автоматов.
Архив прошедших семинаров Добрушинской лаборатории
25.11.2017 | Бланк Михаил Львович |