О колмогоровской сложности конечных подпоследовательностей в последовательности нулей и единиц

• Автор: Румянцев, Андрей Юрьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 88 с. : ил.

Оглавление
Введение

1 Вероятностные доказательства существования

1.1 Основные определения, обозначения и используемые свойства

1.2 Свойства случайных последовательностей

2 Лемма Левина и её обобщения

2.1 Лемма Левина и её обобщение с условной сложностью

2.2 Комбинаторные переформулировки

2.3 Лемма Ловаса и колмогоровская сложность

2.4 Построение последовательности по частям

2.5 Последовательности с повторениями

3 Отрицательные результаты
3.1 Обобщённая лемма Левина и вычислимые перестановки
3.2 Игровой отрицательный результат
3.3 Усиленные результаты
4 Применения
4.1 Критическая экспонента
4.2 Почти периодические последовательности со сложными под-словами
4.3 Последовательности без длинных периодов
4.4 Декодирование списком в терминах колмогоровской сложности
Литература

Введение
-----------------Общая характеристика работы
Актуальность темы.
Диссертация посвящена проблеме построения последовательностей, не нарушающих определённых запрещений; рассматриваются вероятностный, теоретико-сложностной, игровой подходы к данной проблеме.
Теория последовательностей, избегающих различные запрещения, возникла в начале XX века. А. Туэ доказал существование последовательностей, не содержащих квадратов (подслов вида хх, где х — некоторое непустое слово) в троичном алфавите и кубов (подслов вида жет), а также частичных кубов (подслов вида хухух, где х и у — непустые слова), в двоичном алфавите (последовательность Туэ-Морса), см. [7], [8].
Позже началось систематическое исследование последовательностей, не содержащих подслов по определённым шаблонам (например, подслов вида ххуугг, где х,у и г — непустые слова). Недавно эти результаты стали обобщать на частичные последовательности (последовательности, у которых в некоторые местах стоит специальный символ пропуска, означающий, что значение в данной позиции не известно), например, была построена последовательность (без пропусков), которая остаётся последовательностью без кубов при замене любого количества символов на пропуски так, чтобы между соседними пропусками было не менее двух символов (последовательность с пропусками является последовательностью без кубов, если в ней нет подслов, получающихся заменой некоторых символов на пропуски в словах вида ххх, где х — некоторое непустое слово), см. [10].
Также, было введено понятие критической экспоненты последовательности — минимальной верхней грани всех показателей дробных степеней слов, входящих в последовательность (дробная степень слова х с показателем г — это слово вида ххх... хху, где х повторяется столько раз, какова целая часть числа г, а, у — префикс слова х, длина которого рав-

Введение

на дробной части г, умноженной на длину х). Продолжают активно изучаться последовательности с ограничениями на критическую экспоненту, т.е. с запрещениями на подслова, являющиеся степенями с определёнными показателями. В 2007 году Д. Кригер и Дж. Шаллит нашли метод построения последовательностей с заданной критической экспонентой (для любого числа, большего единицы), см. [9].
В 60-х годах XX века было введено понятие колмогоровской сложности. Грубо говоря, колмогоровская сложность строки_-=-это количество-бит в минимальной программе, печатающей эту строку при пустом входе. Появились работы, касающиеся последовательностей, не нарушающих запрещений в каком-либо смысле малой сложности. Так теорема Левина-Шнорра утверждает, что случайная по Мартин-Лёфу последовательность не содержит префиксов малой сложности (вариант с префиксной сложностью появился в 1975-м году, см. [2]). Позже Левин в одной из своих работ по замощениям плоскости ([5]) доказал лемму о том, что существует последовательность, не содержащая подслов малой сложности. В 2003 году Мучник, Семёнов и Ушаков (в [6]) разработали метод построения почти-периодической последовательности без префиксов малой сложности.
Цель работы.
Получить достаточные условия на возможные запрещения для существования последовательности, не нарушающей все эти запрещения и применение полученных результатов для некоторых задач о построении последовательностей.
Методы исследования.
В работе применяются методы теории вероятностей и колмогоровской сложности. Используется Локальная Лемма Ловаса для доказательства совместности событий. Для доказательства некоторых результатов использован метод построения последовательности по частям.
Научная новизна.
Результаты диссертации являются новыми. В диссертации получены следующие основные результаты:
1. Приведено несколько достаточных критериев для возможности построения последовательности, удовлетворяющей определённым ограничениям.
Глава 2. Лемма Левина и её обобщения

состоящее из слов длины не менее N. Из соображений компактности такое множество А можно выбрать конечным (конечным частям А соответствуют замкнутые подмножества канторовского пространства, и если пересечение этих замкнутых подмножеств пусто, то и конечное пересечение пусто). Такое конечное А запрещает не только бесконечные последовательности, но и достаточно длинные конечные (снова применяем компактность), поэтому его при данном N можно найти перебором, и первое подходящее множество будет иметь малую сложностыотносителыю-Л^; при достаточно большом N мы войдём в противоречие со сложностным утверждением (при чуть большем значении а).
Добавление префикса в качестве условия (в обобщённой лемме Левина) также можно перевести на комбинаторный язык, при этом получится такое утверждение:
Теорема 6 (комбинаторный вариант обобщённой леммы Левина). Для любого числа 0 < а < 1 существует 'число N со следующим свойством. Пусть А — произвольное множество пар слов. Причём вторые компоненты пар имеют длину не менее N, и для касисдого слова х и каждого числа п существует не более 2ап слов у длины п, при которых (х, у) £ А. Тогда существует последовательность ш, не имеющая префиксов вида ху, где (х,у) £ А.
(В самом деле, сложностной вариант следует из комбинаторного, если взять множество пар (х, у), для которых у > N и К(у|ж) < ау. В обратную сторону мы берём множество запрещённых пар в качестве оракула. Как и в предыдущем случае, можно обойтись без использования оракула, воспользовавшись компактностью и тем фактом, что первый найденный в ходе перебора объект будет простым.)
Утверждение теоремы 6 можно переформулировать в терминах игры. Первый игрок строит последовательность бит за битом, второй между каждыми двумя ходами первого, а также перед первым его ходом может запретить появление некоторых подслов в некоторых позициях, если эти позиции целиком находятся в ещё не построенной части последовательности. При этом второй может запрещать лишь слова длины не менее N, и в каждой позиции длины п запретить не более 2ап слов. Первый игрок стремится построить бесконечную последовательность, не нарушающую ни одного запрещения, а цель второго — пометать ему.