О колмогоровской сложности конечных подпоследовательностей в последовательности нулей и единиц тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. Ломоносова

Механико-математический факультет

На правах рукописи УДК 519.72

ии^4ИОЗ18

Румянцев Андрей Юрьевич

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

Специальность 01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ 2 2 ОПТ /ГГО

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2009

003480318

Работа выполнена на кафедре математической логики и теории алгоритмов Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических

наук, профессор

Верещагин Николай Константинович.

Официальные оппоненты: доктор физико-математических наук,

профессор Вьюгин Владимир Вячеслович; кандидат физико-математических наук Фрид Анна Эдуардовна.

Ведущая организация: Институт вычислительных технологий Сибирского Отделения РАН.

Защита диссертации состоится 6 ноября 2009 года в 16 часов 45 минут на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: Р.Ф., 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 6 октября 2009 года.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ, доктор физико-математических наук, профессор

А. О. Иванов

Общая характеристика работы

Актуальность темы.

Диссертация посвящена проблеме построения последовательностей, не нарушающих определённых запрещений; рассматриваются вероятностный, те-оретико-сложностной, игровой подходы к данной проблеме.

Теория последовательностей, избегающих различные запрещения, возникла в начале XX века. А. Туэ доказал существование последовательностей, не содержащих квадратов (подслов вида хх, где х — некоторое непустое слово) в троичном алфавите и кубов (подслов вида ххх), а также частичных кубов (подслов вида хухух, где х и у — непустые слова), в двоичном алфавите (последовательность Туэ-Морса)1,2.

Позже началось систематическое исследование последовательностей, не содержащих подслов по определённым шаблонам (например, подслов вида xxyyzz, где х, у и z — непустые слова). Недавно эти результаты стали обобщать на частичные последовательности (последовательности, у которых в некоторые местах стоит специальный символ пропуска, означающий, что значение в данной позиции не известно), например, была построена последовательность (без пропусков), которая остаётся последовательностью без кубов при замене любого количества символов на пропуски гак, чтобы между соседними пропусками было не менее двух символов (последовательность с пропусками является последовательностью без кубов, если в ней нет подслов, получающихся заменой некоторых символов на пропуски в словах вида ххх, где X — некоторое непустое слово)3.

Также, было введено понятие критической экспоненты последовательности — минимальной верхней грани всех показателей дробных степеней слов, входящих в последовательность (дробная степень слова а: с показателем г — это слово вида ххх... хху, где х повторяется столько раз, какова целая часть числа г, а у — префикс слова х, длина которого равна дробной части г, умноженной на длину х). Продолжают активно изучаться последовательности с ограничениями на критическую экспоненту, т.е. с запрещениями на подслова, являющиеся степенями с определёнными показателями. В 2007 году Д. Кри-гер и Дж. Шаллит нашли метод построения последовательностей с заданной критической экспонентой (для любого числа, большего единицы)4.

'Axel Thue, Über unendliche Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 7 (1906) 1-22.

2 Axel Thue, Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1 (1912) 1-67.

'Florin Manea, Robert Merca, Freeness of partial words, Theoretical Computer Science 389, Issue 1-2 (December 2007), pp. 265-277.

4Dalia Krieger, Jeffrey Shallit, Every real number greater than 1 is a critical exponent, Theoretical Computer Science, 381 (issue 1-3, August 2007), pp. 177-182.

В 60-х годах XX века было введено понятие колмогоровской сложности. Грубо говоря, колмогоровская сложность строки — это количество бит в минимальной программе, печатающей эту строку при пустом входе. Появились работы, касающиеся последовательностей, не нарушающих запрещений в каком-либо смысле малой сложности. Так теорема Левина-Шнорра утверждает, что случайная по Мартин-Лёфу последовательность не содержит префиксов малой сложности (вариант с префиксной сложностью появился в 1975-м году5). Позже Левин6 в одной из своих работ по замощениям плоскости доказал лемму о том, что существует последовательность, не содержащая подслов малой сложности. В 2003 году Мучник, Семёнов и Ушаков разработали метод построения почти-периодической последовательности без префиксов малой сложности.

Цель работы.

Получить достаточные условия на возможные запрещения для существования последовательности, не нарушающей все эти запрещения и применение полученных результатов для некоторых задач о построении последовательностей.

Методы исследования.

В работе применяются методы теории вероятностей и колмогоровской сложности. Используется Локальная Лемма Ловаса для доказательства совместности событий. Для доказательства некоторых результатов использован метод построения последовательности по частям.

Научная новизна.

Результаты диссертации являются новыми. В диссертации получены следующие основные результаты:

1. Приведено несколько достаточных критериев для возможности построения последовательности, удовлетворяющей определённым ограничениям.

2. Получены отрицательные результаты, ограничивающие возможность построения последовательностей: доказано, что невозможно построить несколько последовательностей по циклу, каждая из которых обладает

5Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM, 22 (issue 3, July 1975), pp. 329-340

«Bruno Durand, Leonid Levin, Alexander Shen, Complex tilings, STOC Proceedings, 2001, pp. 732-739; enhanced version: http://arXiv.org/abs/cs.CC/0107008

7 Andrei Muchnik, Alexei Semenov and Maxim Ushakov, Almost periodic sequences, Theoretical Computer Science, 304 (issue 1-3, July 2003), pp. 1-33.

условию обобщённой леммы Левина с взятой в качества оракула следующей по циклу последовательностью; доказана невозможность построения последовательности, удовлетворяющей условию обобщённой леммы Левина вместе со своими вычислимыми перестановками (из "основного" достаточного критерия, доказанного в данной работе, следует существование последовательности, удовлетворяющей условию обычной леммы Левина вместе со своими вычислимыми перестановками); доказано, что в одном из игровых вариантов "основного" достаточного критерия игрок, пытающийся построить последовательность, удовлетворяющую некоторым ограничениям, проигрывает.

3. Полученные критерии применены для обобщения теоремы Кригер и Шаллита на частичные последовательности и для построения почти периодических последовательностей, не содержащих подслов малой сложности, а также, для построения многомерного аналога почти периодических последовательностей, не содержащих многомерных подслов малой сложности (т.е. содержимое любого прямоугольного параллелепипеда должно иметь большую сложность).

Теоретическая и практическая ценность.

Работа носит теоретический характер. Результаты, полученные в диссертационной работе, являются развитием методов комбинаторики последовательностей и могут применяться для построения последовательностей с определёнными свойствами. Они могут быть полезны в теории информации, кол-могоровской сложности и комбинаторике последовательностей.

Апробация работы.

Результаты диссертации докладывались на следующих семинарах и конференциях:

• На Колмогоровском семинаре кафедры математической логики и теории алгоритмов механико-математического факультета Московского Государственного Университета имени М. В. Ломоносова под руководством профессора Н. К. Верещагина, профессора А. Л. Семёнова, к.ф.м.н. А. Е. Ромащенко и к.ф.м.н. А. Шеня в 2006 году.

• На международной конференции "Симпозиум по теории и приложениям компьютерных наук" (8ТАС8-2006), Марсель, Франция, 23-25 февраля 2006 года.

• На международной конференции "Колмогоровская сложность и приложения" (Dagstuhl Seminar 06051), Дагштуль, Германия, 29 января - 3 февраля 2006 года.

• На международной конференции "Компьютерные науки в России" (CSR-2007), Екатеринбург, Россия, 3-7 сентября 2007 года.

Публикации.

Основные результаты диссертации опубликованы в трёх работах [1-3].

Структура работы.

Работа состоит из введения, 4 глав, содержащих 14 разделов, и списка литературы. Библиография содержит 17 наименований. Текст диссертации изложен на 88 страницах и содержит 6 иллюстраций.

Краткое содержание диссертации

Предположим, что нам нужно построить бесконечную последовательность нулей и единиц, на которую наложены некоторые ограничения (не содержать подслов определённого вида или не содержать данных комбинаций битов в данных позициях и т.п.)

Если этих ограничений в каком-то смысле немного (отбраковывается мало последовательностей), то можно надеяться, что искомая последовательность существует по количественным соображениям. Например, если суммарная вероятность всех забракованных множеств меньше единицы, то заведомо есть незабракованная последовательность (вероятностное доказательство существования).

В данной работе рассматриваются обобщения этого метода, использующие лемму Ловаса, их переформулировка на языке колмогоровской сложности и применения: построение последовательностей с заданной критической экспо-нентой и построение почти периодических последовательностей со сложными под словами.

В этой работе мы применяем колмогоровскую сложность для доказательства комбинаторных утверждений. Неформально говоря, колмогоровская сложность слова из нулей и единиц — это число битов в кратчайшей программе, печатающей данное слово при пустом входе. Колмогоровская сложность определена с точностью до постоянного слагаемого (см. подробнее в книге Ли и Витаньи8). Можно говорить и о колмогоровской сложности объ-

8Li М., Vitanyi Р, An Introduction to Kolmogorov Complexity and Its Applications, 2nd ed. N.Y.: Springer, 1997.

ектов, не являющихся двоичными словами, надо лишь вычислимо закодировать их такими словами. Например, сложность натурального числа можно определить как сложность его двоичной записи. Обычную колмогоровскую сложность объекта а в данной работе будем обозначать К(а), префиксную сложность будем обозначать КР(а).

Пусть и — бесконечная последовательность нулей и единиц, а X с N — конечное множество индексов. Через ш(Х) мы обозначим двоичное слово, составленное из битов ш с индексами из множества X (записанных слева направо). Мы будем рассматривать ограничения на последовательность и, имеющие такой вид: для данного множества индексов X и для данного слова У требуется, чтобы и>(Х) ф У. Таких ограничений не должно быть слишком много; переходя от количественных формулировок к сложностным, мы требуем, чтобы эти ограничения были в том или ином смысле "просты".

Во введении приводятся основные понятия и обозначения и даётся краткое содержание диссертации.

В главе 1 мы приводим простую переформулировку вероятностного метода (ограничения совместны, если сумма вероятностей запрещённых объектов меньше единицы) в терминах Колмогоровской сложности.

В разделе 1.1 приводятся необходимые определения и свойства колмогоровской и префиксной сложности, а также, случайности по Мартин-Лёфу.

В разделе 1.2 даётся собственно переформулировка вероятностного метода доказательства существования: берём случайную последовательность (в смысле алгоритмической теории вероятностей, то есть определения Мартин-Лёфа) и проверяем, что она удовлетворяет всем ограничениям. В частности, по теореме Левина-Шнорра (в варианте для префиксной сложности) случайная последовательность не содержит префиксов с маленькой сложностью.

Теорема 1 (Левин-Шнорр). Последовательность ш случайна по Мартин-Лёфу тогда и только тогда, когда для некоторого с и для любого целого положительного числа п выполнено неравенство

КР(ш([0,п))) ^ п-с.

Здесь [0,п) обозначает промежуток {0,1,2,...,п — 1}, так что и>([0,га)) есть п-битовое начало последовательности. Мы усиливаем эту теорему в одну сторону, доказывая более сильное свойство случайных последовательностей:

Теорема 2. Пусть последовательностью случайна по Мартин-Лёфу. Тогда для любого конечного множества X С N верно неравенство

КР(ч>{Х),Х)2\Х\-0(1).

Если X = [0, п), то си(Х) определяет X, второй член пары не нужен и мы получаем утверждение "только тогда" теоремы Левина-Шнорра в качестве частного случая. Теорема 2 даёт критерий случайности, инвариантный относительно вычислимых перестановок последовательности.

В главе 2 мы приводим различные более интересные результаты. В разделе 2.1 мы приводим лемму Левина — простой пример, когда вероятностного метода недостаточно, — а затем обобщаем её.

Теорема 3 (лемма Левина). Для любого числа 0 < а < 1 существует такая последовательность и>, что для любых пик выполнено неравенство

K(w([fc, к + та») ^ an -0(1).

Теорема 4 (обобщённая лемма Левина). Для любого числа 0 < а < 1 существует такая последовательность ш, что для любых пик выполнено неравенство

K(u([fc, к + «)) | w([0, к))) >ап- 0(1).

Обобщение леммы Левина опубликовано в [2] (как утверждение 8).

В разделе 2.2 обсуждаются комбинаторная и игровая переформулировки леммы Левина и её обобщения и доказывается их эквивалентность сложност-ным вариантам (как релятивизованным, так и нерелятивизованным).

Теорема 5 (комбинаторный вариант леммы Левина). Для любого числа О < а < 1 существует число N со следующим свойством. Пусть А — произвольное множество слов длины не менее N, элементы которого мы называем "запрещёнными", причём среди слов длины п не больше 2ап запрещённых. Тогда найдётся последовательность из, не содержащая запрещённых подслое.

Эквивалентность комбинаторного и сложностного вариантов леммы Левина доказана в [2] (эквивалентность утверждений 1 и 2).

Теорема 6 (комбинаторный вариант обобщённой леммы Левина). Для любого числа 0 < а < 1 существует число N со следующим свойством. Пусть А — произвольное множество пар слов. И пусть вторые компоненты пар имеют длину не менее N, и для каждого слова х и каждого числа п существует не более 2ап слов у длины п, при которых (х, у) G А. Тогда существует последовательность ш, не имеющая префиксов вида ху, где {х,у) 6 А.

Далее мы переформулируем утверждение теоремы 6 в терминах игры. Первый игрок строит последовательность бит за битом, второй между каждыми двумя ходами первого, а также перед первым его ходом может запретить появление некоторых подслов в некоторых позициях, если эти позиции целиком находятся в ещё не построенной части последовательности. При этом второй может запрещать лишь слова длины не менее N, и в каждой позиции длины п запретить не более 2ап слов. Первый игрок стремится построить бесконечную последовательность, не нарушающую ни одного запрещения, а цель второго — помешать ему.

Теорема 7 (игровая переформулировка обобщённой леммы Левина). Для любого числа 0 < а < 1 существует такое число N, что в описанной игре выигрывает первый игрок.

В разделе 2.3 мы формулируем лемму Ловаса9 и с её помощью доказываем более интересный критерий совместности условий.

Теорема 8 (Локальная лемма Ловаса). Пусть G = (V, Е) — неориентированный конечный граф, V — множество вершин, а Е — множество рёбер. Пусть для каждой вершины указано событие Hv в некотором вероятностном пространстве (одном и том же для ecexv) и число pv 6 (0,1). Предположим, что для любого v событие Hv независимо со случайной величиной, составленной из всех событий Ни для и, не соседних с v, и выполнено неравенство:

Рг(Я„)<р„- Д (1-л).

(v,u)eE

Тогда Рг ( Hv) ^ J} (1 —pv), и, следовательно, это событие не пусто.

4ev ' vev

Применяя эту лемму для множества всех двоичных последовательностей с равномерной бернуллиевской мерой к событиям видаш(Х) — х для некоторых пар (х,Х), где X — конечное множество индексов (натуральных чисел), ai - двоичное слово, мы доказываем следующий комбинаторный результат:

Теорема 9. Для любого числа 0 < а < 1 существует число N со следующим свойством. Пусть А — некоторое множество пар вида (х,Х), называемых "запрещёнными", где X — конечное множество натуральных чисел (индексов), ах— слово длины |Х[. Пусть при этом все слова х в запрещённых парах имеют длину не менее N, и для каждого индекса t и для каждого

9Rajeev Motwani, Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995.

числа п количество запрещённых пар с множествами размерап, содержащими позицию I, не больше 2ап:

Ш,п\{{х,Х)еА\ |Х|=п и г е Х}| ^ 2т.

Тогда существует последовательность ш, не нарушающая ни одного запрещения (для всех (х, X) 6 А выполнено ш(Х) ф х).

Сложностной аналог этой теоремы можно сформулировать следующим образом:

Теорема 10. Для любого 0 < а < 1 существует последовательность и и число с с такими свойствами: в любом конечном непустом множестве X С N найдётся элемент £ £ X, для которого

К{ш(Х),Х\г)>а\Х\-с.

Эта теорема опубликована в [3] (как теорема 1).

По сравнению с теоремой 2 мы усилили утверждение, использовав условную сложность, но одновременно и ослабили его, умножив правую часть на а < 1.

В частности из этого утверждения легко получается многомерный аналог леммы Левина, доказанный М. А. Ушаковым в [2]:

Теорема 12. Пусть а € (0,1). Для любого й ^ \ существует ¿-мерная "последовательность" (отображение —> {0,1}), в которой сложность содержимого любого (целочисленного) параллелепипеда объёма V не меньше -0(1).

Из инвариантности утверждения теоремы 10 относительно вычислимых перестановок последовательности получаем такое утверждение:

Теорема 13. Для любого числа 0 < а < 1 существует такая последовательность и, что для любой вычислимой биекцииа: N —> N перестановка ш с помощью а, то есть последовательность щ = и>„щ, обладает свойством из леммы Левина: для любых пик выполнено неравенство

К{и{[к,к + п)))^ап-0{1).

При этом константа в 0(1) зависит от перестановки, но не зависит от п и

к.

Далее теорема 10 обобщается на случай произвольного алфавита.

Теорема 14. Для любого алфавита А, 2 ^ \А\ < сс и для любого 0 < а < 1 существует последовательность и> в алфавите А и число с с такими свойствами: в любом конечном непустом множестве X С N найдётся элемент < 6 X, для которого

К(и{Х),Х\Ь)>а\Х\1о &\А\-с.

В главе 3 доказываются отрицательные результаты, показывающие невозможность некоторых естественных усилений результатов предыдущих разделов (невозможно совместить в одном утверждении обобщение леммы Левина и критерий, который даёт теорема 10). В разделе 3.1 приводится доказательство того, что нельзя усилить обобщённую лемму Левина так, чтобы она стала инвариантна относительно вычислимых перестановок.

Рассмотрим (очевидно, вычислимую) перестановку

_ ( 0 12 345 6 7 8 9 -Л ^ V 0 21 543 9 8 7 6

которая разбивает натуральный ряд на отрезки длин 1,2,3,4,... и переворачивает каждый отрезок в обратном порядке.

Теорема 18. Для любой двоичной последовательности из в одной из последовательностей ш и сги> найдётся сколь угодно длинное подслово сложности 0(1) относительно соответствующего префикса.

Таким образом, инвариантный относительно вычислимых перестановок вариант обобщённой леммы Левина не верен (аналогичный инвариантный вариант обычной леммы Левина верен в силу теоремы 13).

Далее доказывается, что не существует пара последовательностей, каждая из которых обладала бы свойством теоремы 4 с взятой в качестве оракула другой последовательностью. А также пары последовательностей, каждая из которых обладала свойством теоремы 10 с взятой в качестве оракула другой последовательностью.

Теорема 20. Для любой пары бесконечных последовательностей нулей и единиц хотя бы одна из них содержит сколь угодно длинные подслова сложности 0(1) относительно их позиции с взятой в качестве оракула другой последовательностью.

В разделе 3.2 мы формулируем игровой аналог утверждения теоремы 9 (подобно тому как теорема 7 была игровым вариантом теоремы 4).

Первый игрок, как и раньше, строит последовательностью бит за битом. Второй игрок между каждыми двумя ходами первого (а также перед первым

его ходом) может запретить выполнение равенства oj(X) = х для некоторых пар (ж, X), где X — конечное множество индексов, не пересекающееся с уже построенным началом последовательности, ах — слово длины |Х|. При этом запрещения должны удовлетворять ограничениям, описанным в формулировке теоремы 9. Первый игрок стремится построить бесконечную последовательность, не нарушающую ни одного запрещения, а цель второго — помешать ему. Доказывается, что первый игрок не может выиграть в этой игре, даже если дополнительно ограничить права второго игрока, разрешив ему делать только запрещения со словами х некоторой фиксированной длины N и потребовав, чтобы каждый индекс t входил не более чем в два запрещения.

Теорема 21. Для любого числа N > 0 и любого а < 1 в описанной игре первый игрок проигрывает.

В главе 4 содержатся приложения результатов диссертации. В разделе 4.1 мы обобщаем результат Д. Кригер и Дж. Шаллита, используя теорему 10.

Пусть а — некоторое слово (не обязательно в двоичном алфавите), аЬ — его префикс (начало). Тогда слово с = ааа...ааЬ называется дробной степенью слова а, а число г = — показателем этой степени. Пишут с = аГ. Критическая экспонента некоторой последовательности w — это точная верхняя грань всех показателей степеней, являющихся подсловами в этой последовательности. Д. Кригер и Дж. Шаллит доказали следующую теорему:

Теорема 27 (Кригер, Шаллит). Для любого числа г > 1 существует последовательность и} (не обязательно в двоичном алфавите), которая имеет критическую экспоненту г.

Мы для данного числа г > 1 строим последовательность, которая содержит степени слов с показателями, меньшими г, и не содержит степеней слов с показателями, большими г, и, более того, даже подслов, близких в смысле расстояния Хемминга к степеням слов с показателями, большими г.

Теорема 28. Для любого действительного числа г > 1 существует число е > 0 и последовательность, критическая экспонента которой равна г, которая ни для какого s > г не содержит подслова, minje, -близкого к степени с показателем s.

Эта теорема усиливает результат, опубликованный в [3] (там доказывалась теорема с более слабым условием: последовательность ни для какого s > r+S

не содержит подслова, е-близкого к степени с показателем s, где S — положительное число, которое можно выбрать сколь угодно малым, а е зависит как от г, так и от <$).

Аналогичное утверждение имеет место для частичных последовательностей, при этом малое расстояние Хемминга будет соответствовать малому числу пропусков. Частичная последовательность в некотором алфавите — это частичное отображение из множества натуральных чисел в этот алфавит. Частичное слово — это частичное отображение из начального отрезка натуральных чисел в алфавит (слово, у которого определены не все буквы), удобно при этом при записи вместо неопределённой буквы писать специальный символ пропуска о. Будем говорить, что одно частичное слово включает другое, если длины этих слов одинаковы, и выполнено соответствующее включение одного частичного отображения в другое. Критическая экспонента частичной последовательности — это точная верхняя грань всех показателей степеней, включающих подслова в этой последовательности, за исключением (вырожденных) включений подслов вида XqXi ... х^-гО и ох\... Xk-iXo в степень с показателем (к + 1 )/к, где хо,..., Xk-i ф о (такие включения в степени невозможно избежать, если в последовательности есть неопределённые символы). Недавно было доказано, что существует более, чем счётное количество бесквадратных (за исключением квадратов вида ао и оа, где а ф о) частичных последовательностей с бесконечным количеством пропусков в троичном алфавите10, т.е. существуют частичные последовательности с критической экспонентой, не большей двух. Мы доказываем близкую теорему, про критическую экспоненту частичных слов (не ограничивая размер алфавита):

Теорема 29. Для любого действительного числа г > 1 существует число M 6 N и (всюду определённая) последовательность, критическая экспонента которой равна г и не изменяется при замене любого количества символов в последовательности на пропуски так, чтобы между соседними пропусками было не меньше M символов.

Эта теорема не является прямым следствием предыдущей, однако, её доказательство основано на тех же идеях.

В разделе 4.2 мы приводим конструкцию почти периодической последовательности, не имеющей простых подслов (то есть подслов х, для которых К(ж) < a|i| -0(1) для некоторой константы а < 1) и её многомерный аналог.

10Vesa Haiava, Tero Harju and Tomi Kärki, Square-free partial words, Information Processing Letters, Volume 108, bsue 5 (15 November 2008), pp. 290-292.

Мы называем ¿-мерными двоичными последовательностями, отображения вида V : Zd —> В, ¿-мерным словом — прямоугольный параллелепипед из символов (без фиксированной позиции его в пространстве), размером ¿-мерного слова — число символов в нём, а подсловами ¿-мерной последовательности — ¿-мерные слова, взятые из прямоугольных параллелепипедов в последовательности.

Бесконечную á-мерную последовательность v из нулей и единиц мы называем почти периодичной, если для любого подслова в этой последовательности найдётся такое число к, что это подслово входит в любой куб со стороной к в этой последовательности (это определение соответствует сильной почти-периодичности в одномерном случае).

Теорема 30. Для любого а 6 (0,1) существует почти периодическая d-мерная последовательность v : Zd —> В, у которой сложность любого подслова размера m не меньше am — 0(1).

Эта теорема усиливает результат, опубликованный в [2] (там она была доказана только для кубов, а не для произвольных прямоугольных параллелепипедов).

В разделе 4.3 изучается величина11 R(a,l), где а ^ 2 и / ^ 1, определяемая как точная нижняя грань всех таких чисел г, для которых существует последовательность в a-символьном алфавите, не содержащая дробных степеней слов xv для |х| ^ I и р ^ г. Теперь мы рассматриваем дробные степени с ограничением на длину слова х.

Сначала доказывается простая нижняя оценка:

R(a,l)Z 1 + 1

Затем доказывается обобщение на случай произвольного алфавита известной теоремы12.

Теорема 31. Для любого размера алфавита а ^ 2 и любого положительного действительного числа Ь < а существует число N и последовательность и в алфавите из а символов такая, что для любого п ^ N расстояние между любыми двумя различными вхождениями одного и того же слова длины п в эту последовательность будет не меньше Ьп.

uLucian Die, Pascal Ochem, Jeffrey Shallit, A Generalization of Repetition Threshold, Mathematical foundations of computer science, 345, Issue 2-3 (November 2005), pp. 359-369.

12J. Berk, An application of Lovász local lemma: there exists an infinite 01-sequence containing no near identical intervals. In A. Hajnal, L. Lovász, and V. T. Sós, editors, Finite and Finite Sets, Vol. 37 of Colloq. Math. Soc. János Bolyai, 1981, pp. 103-107.

В частности, из этой теоремы получается такая верхняя оценка: для любого целого а и действительного Ъ таких, что 1 < Ь < а, для достаточно больших I выполнено

Я(а,0 <1 + ^.

После этого даётся следующая усиленная оценка для функции R.

Теорема 33. Существует такая константа с, что для любых а ^ 2 и выполнено

В разделе 4.4 приводится ещё один пример применения колмогоровской сложности для доказательства комбинаторных утверждений. Мы формулируем на языке колмогоровской сложности результаты из теории кодирования.

Одним из важных понятий теории кодирования является декодирование списком. Пусть / — функция из {0,1}* в {0,1}", называемая фукнцией кодирования. Тогда декодирование списком, исправляющее рп ошибок, где О < р < 1, это отображение, сопоставляющее каждому двоичному слову х длины п список всех слов длины к, для которых образ под действием функции / лежит на расстоянии (по Хеммунгу) не более рп от слова х. Ясно, что если существуют такие 2к слов длины п, что любой шар Хемминга радиуса рп содержит не более L из них, то существует функция кодирования f позволяющая декодировать списком длины не более L.

Говоря о колмогоровской сложности, мы рассматриваем "устойчивые" относительно изменения не более чем в рп битах слова, т.е. такие слова х, для которых К(х | у) мало для любого слова у, отличающегося от х не более чем в рп позициях. Связь существования таких слов с возможностью декодирования списком (ограниченной длины) показывается такой теоремой.

Теорема 35. Пусть фиксированы р <^,k<nuL< 2". Тогда справедливы следующие утверждения.

А. Если существуют такие 2к слов длины п, что любой шар Хемминга радиуса рп содержит не более L из них, то существует такое слово х длины п и сложности не менее k — 0(\ogn), что для любого слова у, отличающегося от х не более чем в рп битах, имеет место оценка К(х | у) < logL Ч- O(logn).

Б. Если существует такое слово х длины п и сложности не менее к, что для любого слова у, отличающегося от х не более чем в рп битах, Щя I у) l°gL, то существуют такие 2i_0(losn) слов длины п, что любой шар Хемминга содержит не более L • из них.

Эта теорема опубликована в [1] (как теорема 2).

Из теории кодирования известно13 существование таких множеств (как в пункте Б теоремы) с определёнными значениями констант. Мы, однако, приводим другой вариант доказательства этого утверждения, основанный на колмогоровской сложности.

Теорема 36. Пусть фиксировано число р < 1/2 и а — 1 — Н(р). Тогда для любого п можно найти слово х длины п, для которого

(а) К(х) = ап + O(logn);

(б) К(ж I у) — O(logn) для любого слова у, отличающего от х не более чем в рп позициях.

(Здесь константа в обозначении О (log rt) может зависеть от р, но не от п и у.) Эта теорема опубликована в [1] (как теорема 3).

Благодарности.

Автор благодарит своих научных руководителей д.ф.м.н., профессора Н. К. Верещагина и к.ф.м.н. А. Шеня за постановку задач и постоянную помощь. Автор благодарен руководителям и участникам Колмогоровского семинара, а также сотрудникам кафедры математической логики и теории алгоритмов за полезные обсуждения работы.

Список литературы

[1] А. Ю. Румянцев, Передача информации по каналу с ошибками с точки зрения колмогоровской сложности, Вестник Московского университета, Серия 1, Математика, Механика, 2006, 1.С., стр. 54-56.

[2] Andrey Yu. Eumyantsev, Maxim A. Ushakov, Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences, Springer, Lecture Notes in Computer Science, Volume 3884 / 2006, STACS 2006, pp. 396-407.

[3] Andrey Yu. Rumyantsev, Kolmogorov Complexity, Lovdsz Local Lemma and Critical Exponents, Springer, Lecture Notes in Computer Science, Volume 4649 / 2007, CSR 2007, pp. 349-355.

В работе [2] А. Ю. Румянцеву принадлежат утверждения 6-9, а также лемма и следствие в конце раздела 4; М. А. Ушакову принадлежит утверждение 4.

1ЭМак-Вильямс Ф. Дж., Слоэн Н. Дж. А., Теория кодов, исправляющих ошибки, М.: Радио и связь, 1979.

Подписано в печать 06, /О. О9 Формат 60x90 1/16. Усл. печ. л. ¿V Тираж -/01? экз. Заказ 35

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета. МГУ имени М.В.Ломоносова

Введение

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].

Позже началось систематическое исследование последовательностей, не содержащих подслов по определённым шаблонам (например, подслов вида xxyyzz, где х,у п непустые слова). Недавно эти результаты стали обобщать на частичные последовательности (последовательности, у которых в некоторые местах стоит специальный символ пропуска, означающий, что значение в данной позиции не известно), например, была построена последовательность (без пропусков), которая остаётся последовательностью без кубов при замене любого количества символов на пропуски так, чтобы между соседними пропусками было не менее двух символов (последовательность с пропусками является последовательностью без кубов, если в ней нет подслов, получающихся заменой некоторых символов на пропуски в словах вида ххх, где х — некоторое непустое слово), см. [10].

Также, было введено понятие критической экспоненты последовательности — минимальной верхней грани всех показателей дробных степеней слов, входящих в последовательность (дробная степень слова х с показателем г — это слово вида ххх. хху, где х повторяется столько раз, какова целая часть числа г, а у — префикс слова ж, длина которого равна дробной части г, умноженной на длину х). Продолжают активно изучаться последовательности с ограничениями на критическую экспоненту, т.е. с запрещениями на подслова, являющиеся степенями с определёнными показателями. В 2007 году Д. Кригер и Дж. Шаллит нашли метод построения последовательностей с заданной критической экспонентой (для любого числа, большего единицы), см. [9].

В 60-х годах XX века было введено понятие колмогоровской сложности. Грубо говоря, колмогоровская^сложность^строки-^=~это-количество-бит" в^минимальной программе, печатающей эту строку при пустом входе. Появились работы, касающиеся последовательностей, не нарушающих запрещений в каком-либо смысле малой сложности. Так теорема Левина-Шнорра утверждает, что случайная по Мартин-Лёфу последовательность не содержит префиксов малой сложности (вариант с префиксной сложностью появился в 1975-м году, см. [2]). Позже Левин в одной из своих работ по замощениям плоскости ([5]) доказал лемму о том, что существует последовательность, не содержащая подслов малой сложности. В 2003 году Мучник, Семёнов и Ушаков (в [6]) разработали метод построения почти-периодической последовательности без префиксов малой сложности.

Цель работы.

Получить достаточные условия на возможные запрещения для существования последовательности, не нарушающей все эти запрещения и применение полученных результатов для некоторых задач о построении последовательностей.

Методы исследования.

В работе применяются методы теории вероятностей и колмогоровской сложности. Используется Локальная Лемма Ловаса для доказательства совместности событий. Для доказательства некоторых результатов использован метод построения последовательности по частям.

Научная новизна.

Результаты диссертации являются новыми. В диссертации получены следующие основные результаты:

1. Приведено несколько достаточных критериев для возможности построения последовательности, удовлетворяющей определённым ограничениям.

2. Получены отрицательные результаты, ограничивающие возможность построения последовательностей: доказано, что невозможно построить несколько последовательностей по циклу, каждая из которых обладает условию обобщённой леммы Левина с взятой в качества оракула следующей но циклу последовательностью; доказана невозможность построения последовательности, удовлетворяющей условию обобщённой леммы Левина вместе со своими вычислимыми перестановками (из "основного" достаточного критерия, доказанного в данной работе,"следует существование последовательности, удовлетворяющей условию обычной леммы Левина вместе со своими вычислимыми перестановками); доказано, что в одном из игровых вариантов "основного" достаточного критерия игрок, пытающийся построить последовательность, удовлетворяющую некоторым ограничениям, проигрывает.

3. Полученные критерии применены для обобщения теоремы Кригер и Шаллита на частичные последовательности и для построения почти периодических последовательностей, не содержащих подслов малой сложности, а также, для построения многомерного аналога почти периодических последовательностей, не содержащих многомерных подслов малой сложности (т.е. содержимое любого прямоугольного параллелепипеда должно иметь большую сложность).

Теоретическая и практическая ценность.

Работа носит теоретический характер. Результаты, полученные в диссертационной работе, являются развитием методов комбинаторики последовательностей и могут применяться для построения последовательностей с определёнными свойствами. Они могут быть полезны в теории информации, колмогоровской сложности и комбинаторике последовательностей.

Апробация работы.

Результаты диссертации докладывались на следующих семинарах и конференциях:

• На Колмогоровском семинаре кафедры математической логики и теории алгоритмов механико-математического факультета Московского Государственного Университета имени М. В. Ломоносова под руководством профессора Н. К. Верещагина, профессора А. Л. Семёнова, к.ф.м.н. А. Е. Роматценко и к.ф.м.н. А. Шеня в 2006 году.

• На международной конференции "Симпозиум по теории и приложениям компьютерных наук" (STACS-2006), Марсель, Франция, 23-25 февраля 2006 года.

• На международной конференции "Колмогоровская сложность и приложения" (Dagstuhl Seminar 06051), Дагштуль, Германия, 29 января -3 февраля 2006 года.

• На международной конференции "Компьютерные науки в России!! (CSR-2007), Екатеринбург, Россия, 3-7 сентября 2007 года.

Публикации.

Основные результаты диссертации опубликованы в трёх работах [1517], из них одна работа в журнале из перечня ВАК.

Структура работы.

Работа состоит из введения, 4 глав, содержащих 14 разделов, и списка литературы. Библиография содержит 17 наименований. Текст диссертации изложен на 88 страницах и содержит 6 иллюстраций.

1. Li М., Vitanyi Р, An 1.troduction to Kolmogorov Complexity and Its Applications, 2nd ed. N.Y.: Springer, 1997.

2. Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM, 22 (issue 3, July 1975), pp. 329340.

3. А. К. Звонкин, JI. А. Левин, Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов, УМН, 25:6(156), 1970, стр. 85-127.

4. Rajeev Motwani, Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995.

5. Bruno Durand, Leonid Levin, Alexander Shen, Complex tilings, STOC Proceedings, 2001, pp. 732-739; enhanced version: http://arXiv.org/abs/cs.CC/0107008

6. Andrei Muchnik, Alexei Semenov and Maxim Ushakov, Almost periodic sequences, Theoretical Computer Science, 304 (issue 1-3, July 2003), pp. 1 33.

7. Axel Thue, fiber unendliche Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 7 (1906) 1-22.

8. Axel Thue, Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1 (1912) 1-67.

9. Dalia Krieger, Jeffrey Shallit, Every real number greater than 1 is a critical exponent, Theoretical Computer Science, 381 (issue 1-3, August 2007), pp. 177-182.Литература

10. Florin Manea, Robert Merca, Freeness of partial words, Theoretical Computer Science, 389, Issue 1-2 (December 2007), pp. 265-277.

11. Vesa Halava, Tero Harju and Tomi Karki, Square-free partial words, Information Processing Letters, Volume 108, Issue 5 (15 November 2008), pp. 290-292.

12. Lucian Ilie. Pascal Ochem, Jeffrey Shallit, A Generalization of Repetition Threshold, Mathematical foundations of computer science, 345, Issue 2-3 (November 2005), pp. 359-369.

13. Мак-Вильямс Ф. Дж., Слоэн H. Дж. А., Теория кодов, исправляющих ошибки, М.: Радио и связь, 1979.

14. А. Ю. Румянцев, Передача информации по каналу с ошибками с точки зрения колмогоровской сложности, Вестник Московского университета, Серия 1, Математика, Механика, 2006, 1.С., стр. 54-56.

15. Andrey Yu. Rumyantsev, Maxim A. Ushakov, Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences, Springer, Lecture Notes in Computer Science, Volume 3884 / 2006, STACS 2006, pp. 396407.

16. Andrey Yu. Rumyantsev, Kolmogorov Complexity, Lovasz Local Lemma and Critical Exponents, Springer, Lecture Notes in Computer Science, Volume 4649 / 2007, CSR 2007, pp. 349-355.