Нормальные последовательности и автоматная сложность

Хорошо известно, что нормальные последовательности (те, где любая группа цифр встречается с одинаковой предельной частотой) можно описать как несжимаемые с помощью конечных автоматов. Однако стандартная формулировка критерия такого рода (Becher, Heiber, 2014) не соответствует общей схеме определения несжимаемости в терминах колмогоровской сложности. Этот критерий можно переформулировать, введя понятие автоматной сложности, и тогда классические результаты о нормальных последовательности (сохранение нормальности двоичного числа при умножении на рациональное, эквивалентность разных определений, а также теорема Пятецкого-Шапиро о нормальности последовательности, в которой частоты появления всех блоков не более чем в константу раз превосходят ожидаемые) получают простые и естественные доказательства в терминах конечных автоматов.