Структура распределения информации в бесконечной последовательности

Ставится задача изучения структуры распределения информации в бесконечных последовательностях. Для ее решения предложен подход, основанный на восстановлении последовательности по ее подпоследовательности. Для реализации этого подхода вводится необходимый инструментарий, в частности, понятия жесткой и плотно упакованной последовательностей, характеризующие степень дублирования информации в последовательности. Рассматривается автоматная модель, в рамках которой доказано существование плотно упакованных и жестких последовательностей и установлен ряд их свойств, в частности, связь со сложностью предсказания очередного элемента последовательности. Продемонстрирована возможность применения полученных результатов к изучению структуры степеней автоматных преобразований, доказано, что любое конечное частично упорядоченное множество с наименьшим и наибольшим элементами изоморфно начальному сегменту структуры степеней автоматных преобразований последовательностей в алфавите $\{0,1\}$. В статье обсуждается отношение полученных результатов к теории информации и кодирования.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант 93–011–16004.