«Сверхслова, меры на них и их полупрямые произведения ...»

ФГБОУ ВПО «Московский государственный университет имени М.В.

Ломоносова»

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

На правах рукописи

Раскин Михаил Александрович

Сверхслова, меры на них и их полупрямые

произведения

01.01.06 – математическая логика, алгебра и теория чисел

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

Научный руководитель д. ф.-м. н., профессор Николай Константинович Верещагин Москва – 2014 2 Содержание Введение................................... Глава 1. Действие конечного автомата на почти периодическом сверхслове................................. 1.1. Поведение регулятора почти периодичности........... 1.2. Почти периодические сверхслова и конечные автоматы..... 1.3. Основной результат о почти периодических сверхсловах.... 1.4. Конструкция требуемого сверхслова................ 1.5. Базовые свойства конструкции................... 1.6. Позиции вхождений слов в сверхслово и их остатки от деления на.................................. 1.7. Нижняя оценка на регулятор почти периодичности прямого произведения построенного сверхслова и периодического сверх­ слова................................. 1.8. Верхняя оценка регулятора построенного сверхслова...... 1.9. Завершение доказательства..................... 1.10. Улучшение нижней оценки теоремы 0.2.............. Глава 2. Полупрямые произведения вычислимых мер на сверх­ словах................................... 2.1. Основные свойства полупрямых произведений, согласованных с отношением............................. 2.2. Основной результат.......................... Глава 3. Меры на сверхсловах и клеточные автоматы..... 3.1. Постановка задачи.......................... 3.2. Используемые базовые понятия и обозначения.......... 3.3. Инвариантные меры и операторы на них............. 3.4. Определение оператора Ann.................... 3.5. Частичный порядок на инвариантных мерах......... 3.6. Частичный порядок на инвариантных мерах......... 3.7. Основной результат......................... 3.8. Возможные применения отношения............... Список литературы............................ Список публикаций автора по теме диссертации............ Введение 0.1. Регуляторы почти периодических последовательностей В первой главе диссертации изучается вопрос о нижних оценках для регулятора почти периодичности автоматного образа почти периодической последовательности, в частности, прямого произведения периодической и по­ чти периодической последовательности.

Нестрого говоря, последовательность называется почти периодической, если для всякого слова, которое в ней встречается, расстояние между сосед­ ними вхождениями ограничено сверху некоторой функцией (регулятором) от длины слова. Понятие почти периодичности было введено А. Туэ в начале XX века.

В работах к.ф.-м.н. Ан. А. Мучника, акад. РАН проф. А.Л. Семёнова и к.ф.-м.н. М.А. Ушакова, а позже к.ф.-м.н. Притыкина, изучалось действие ко­ нечно-автоматных преобразователей на почти периодических последователь­ ностях. Было известно, что образ почти периодической последовательности под действием конечно-автоматного преобразования является почти периоди­ ческим, но верхняя оценка на регулятор образа казалась избыточной.

В первой главе доказывается нижняя оценка аналогичная ранее извест­ ной верхней.

Основные определения Определение 0.1. Пусть дан некоторый алфавит. Словом над этим алфа­ витом называется конечная последовательность букв (элементов алфавита).

Сверхсловом называется бесконечная последовательность букв. Мы считаем, что буквы в сверхслове занумерованы элементами N; в последующих главах мы будем называть двусторонними сверхсловами бесконечные двусторонние последовательности букв, то есть отображения из Z в.

Сверхслово 1, 2,...,,... называется периодическим, если для неко­ торого целого положительного числа при всех выполняется равенство = +. Как обычно, наименьшее такое число называется периодом.

Определение 0.2. Слово входит в сверхслово с ограниченными ин­ тервалами, если существует такое число, что каждый отрезок сверхслова длины содержит вхождение слова.

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

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

выходное слово при этом будет = 0 1....

Замечание 0.1. Мы рассматриваем здесь то же определение, что использу­ ется в работах Ю.Л. Притыкина.

История рассматриваемых понятий Понятие почти периодичности сверхслов было введено в рассмотрение А. Туэ в начале XX века как ослабление понятия периодичности. В частно­ сти, А.Туэ использовал это понятие при описании свойств последовательно­ сти Туэ-Морса 0110100110010110.... Это сверхслово получается, если начать со слова 0 и бесконечное число раз приписывать к уже имеющемуся слову ре­ зультат замены в нём 1 на 0 и 0 на 1.

Другим известным примером почти периодических сверхслов являются последовательности Штурма. По определению, каждая последовательность Штурма описывает последовательность пересечений некоторого луча с ирра­ циональным тангенсом угла наклона с вертикальными и горизонтальными линиями на бесконечной клетчатой бумаге: идя вдоль луча от его начала, мы записываем ноль, когда пересекается горизональный отрезок, и записы­ ваем единицу, когда пересекается вертикальный отрезок. Если тангенс угла наклона рационален, то возникающая таким образом последовательность ну­ лей и единиц периодична. Иначе она не периодична, но является почти пери­ одической. Сверхслова Штурма имеют следующее интересное свойство: для каждого натурального числа любая последовательность Штурма содержит ровно + 1 различных подслов длины. Более того, любая последователь­ ность с этим свойством обязательно есть последовательность Штурма (см., например, учебник [1]).

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

Понятие почти периодичности тоже можно обобщить.

Определение 0.3. Сверхслово называется заключительно (почти) перио­ дическим, если при удалении из него некоторого начала остаётся (почти) периодическое сверхслово.

Сверхслово называется обобщённо почти периодическим, если каж­ дое слово либо встречается в конечное число раз, либо входит в с ограниченными интервалами. При этом для обобщённо почти периодических слов регулятор надо определять немного не так, как для почти периодиче­ ских. Регулятором в общем случае называется минимальная такая функция : N N, такая что для каждого любое слово длины либо входит в каждый отрезок сверхслова длины () либо не входит в сверхслово, начиная с позиций с номерами, большими чем значение (). Легко видеть, что регулятор любой почти периодической последовательности совпадает с регулятором её почти периодичности, определённым ранее.

Например, сверхслово 0111... является заключительно периодическим, но не почти периодическим. А сверхслово 00000110100110010110... (получен­ ное добавлением четырех нулей к последовательности Туэ–Морса) является заключительно почти периодическим, но не является заключительно пери­ одическим. В работе [2] показано существование обобщённо почти периоди­ ческого слова, не являющегося почти периодическим и даже заключительно почти периодическим.

В работах Ан.А. Мучника, А.Л. Семёнова, М.А. Ушакова и Ю.Л. При­ тыкина изучался вопрос сохранения почти периодичности под действием раз­ личных преобразований.

В [3] показано, что если подавать конечному автомату на вход обобщен­ но почти периодическое сверхслово, то на выход он будет выдавать обобщен­ но почти периодическое сверхслово. В [2] доказан аналог этого результата для более узкого класса: показано, что заключительно почти периодические сверхслова под действием конечного автомата переходят в заключительно почти периодические.

Эти результаты сделали естественным вопрос о том, как при этом из­ меняется регулятор. Если рассмотреть проекцию, то есть конечно-автомат­ ное преобразование с одним состоянием, то регулятор не может увеличиться.

В [3, 4] фактически получена в общем случае верхняя оценка регулятора конечно-автоматного образа через регулятор исходного сверхслова. Но эта оценка очень быстро растет.

Будем обозначать через (·) функцию, являющуюся -кратной компо­ зицией функции (·) с собой: () = ( (... ( )... )).

Теорема 0.1 ([3, 4]). Если у заключительно почти периодического сверх­ слова регулятор не превосходит () 1 и автомат имеет состояний, то у его образа под действием автомата регулятор (в смысле определения 0.3) не превосходит ().

Определение 0.4. Прямым произведением двух сверхслов = 1 2... и = 1 2... называется сверхслово, состоящее из пар соответствующих сим­ волов в сверхсловах и, то есть сверхслово (1, 1 )(2, 2 )... Аналогично определяется прямое произведение конечных слов одной длины. Алфавитом прямого произведения сверхслов является декартово произведение исходных алфавитов.

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

На докладе [5], в котором были доказаны основные результаты [2, 4], М.Н. Вялый поставил вопрос о возможности уменьшения верхней оценки.

После того, как ответ на этот вопрос был дан автором диссертации, А.Л. Се­ мёнов поставил вопрос о том, для какого класса конечных автоматов можно провести аналогичное рассуждение.

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

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

Основной результат главы Основной результат, представленный в первой главе — существование почти периодического слова с регулятором (·), прямое произведение которо­ го с периодическим словом с периодом имеет регулятор вида ().

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

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

Теорема 0.2. (опубликовано в [16]) Если задана возрастающая функция на­ турального аргумента, то существует почти периодическое сверхсло­ во нулей и единиц со следующими свойством. Для всех > 100 и беско­ нечно многих значение на регулятора почти периодичности сверхслова Cycle превышает (max{, } + 1) 30 (), где Cycle обозначает сверх­ слово ( mod ), а — регулятор почти периодичности сверхслова.

Данные свойства сохраняются и при выкидывании произвольного нача­ ла из сверхслова.

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

Теорема 0.3. Пусть задана возрастающая функция : N N. Тогда най­ дётся почти периодическое сверхслово с регулятором почти периодично­ сти и следующими свойствами.

1) Для бесконечного количества аргументов превышает. Более того, эти аргументы выстроены в цепочку: существует последователь­ ность натуральных чисел, такая что 2) Для любого > 2 и любого регулятор почти периодичности Cycle удовлетворяет неравенствам Cycle ( ) > +2 ( ).

3) Для любого достаточно большого регулятор почти периодично­ сти всё того же прямого произведения Cycle на всех достаточно больших значениях аргументов превышает.

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

0.2. Вычислимость полупрямых произведений вычислимых мер, согласованных с отношением порядка Во второй главе изучается вопрос о вычислимости полупрямого произ­ ведения вычислимых мер на сверхсловах, согласованного с отношением по­ рядка, индуцированного порядком на алфавите. Данный вопрос был постав­ лен А. Шенём на докладе [6]. Доказывается существование двух конкретных вычислимых мер, у которых есть полупрямое произведение, согласованное с отношением порядка, но любое такое полупрямое произведение невычислимо.

Основные определения Определение 0.5. Пусть имеются вероятностные меры, на простран­ ствах,. Напомним, что прямым произведением мер, называется мера на прямом произведении пространств, такая, что для любых изме­ римых множеств и выполнено равенство Говорят, что мера на пространстве является полупрямым произве­ дением и, если ее проекции равны и, то есть, для любого измеримого выполнено а также, для любого измеримого выполнено Примером полупрямого произведения мер, является их прямое произве­ дение.

Определение 0.6. Пусть заданы конечные множества, и распределения вероятностей и на и, соответственно. Пусть также задано некото­ рое бинарное отношение. Будем говорить, что распределение находится в отношении с, если существует полупрямое произведение и, относительно которого множество пар имеет вероятность 1. Такое полупрямое произведение будем называть согласованным с.

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

Определение 0.7. Напомним стандартное определение вычислимой меры.

Рассмотрим множество = {0, 1}. Через N обозначим пространство сверхслов из нулей и единиц. Введем на нем покомпонентный частичный по­ рядок: 0 1 2... 0 1 2..., если при всех. Будем рассматривать ме­ ры, заданные на сигма-алгебре, порожденной множествами сверхслов, являю­ щихся продолжениями заданных конечных слов. Мера на пространстве N называется вычислимой, если существует алгоритм, который по Q, > 0, и конечному слову в алфавите находит с точностью меру множества всех бесконечных продолжений (см., например, [7]). Аналогично определя­ ются меры и их вычислимость на пространстве N N : измеримыми яв­ ляются элементы сигма-алгебры, порожденной множествами пар сверхслов, первое из которых является продолжением одного слова, а второе — другого слова. Алгоритм должен по > 0 и словам, находить с точностью меру множества всех пар, в которых первая компонента продолжает слово, а вторая — слово.

Для вычислимости вероятностной меры достаточно существования ал­ горитма порождения этого распределения как выхода вероятностного алго­ ритма. Точнее, распределение на N вычислимо, если существует вероят­ ностный алгоритм (алгоритм, имеющий доступ к независимым бросаниям симметричной монеты) без входа, который на выходной ленте печатает слу­ чайную бесконечную последовательность с распределением.

Существование полупрямых произведений, согласованных с отношениями Из теоремы Форда–Фалкерсона [8] о максимальном потоке и разрезе следует следующий простой критерий того, что распределение находится в отношении с, приведённый, например, в работе [9]:

Теорема 0.4. [Автор неизвестен] Распределение находится в отношении с, тогда и только тогда, когда не существует подмножеств,, таких что все -соседи лежат в и () > ().

Если же = и — отношение порядка (транзитивное рефлексивное отношение), то критерий можно переформулировать так: () () для всякого замкнутого вверх множества. (В самом деле, можно считать, что состоит только из соседей, тогда оно замкнуто вверх в силу транзи­ тивности отношения порядка и содержит в силу рефлексивности, а значит можно замкнуть вверх.) Применение полупрямых произведений мер и история рассматриваемого вопроса Полупрямые произведения, согласованные с отношением порядка, явля­ ются одним из примеров применения полупрямых произведений, не являю­ щихся прямыми. Например, нам может понадобиться, чтобы случайная пара (, ) с большой вероятностью относительно полупрямого произведения об­ ладала некоторым “хорошим” свойством. Мы приведём три таких примера, Пример 1. Даны распределения вероятности, на одном и том же ко­ нечном множестве. Требуется найти их полупрямое произведение, для которого вероятность события “первая координата совпадает со второй” мак­ симальна. Эта задача возникает при доказательстве некоторого неравенства, ограничивающего разницу между шенноновской энтропией и в терминах статистического расстояния между и (см. [7]).

Пример 2. Одним из двух известных методов получения не шеннонов­ ских информационных неравенств является «метод независимизации», при­ мененный в [9, 10]. Мы изложим этот метод вкратце, а для более подробного знакомства отсылаем читателя к книге [7]. В простейшей ситуации метод со­ стоит в следующем: пусть дано некоторое неравенство, в которое входит шен­ ноновские энтропии случайных величин, и, шенноновская энтропия пары случайных величин (, ) и шенноновская энтропия пары случайных величин (, ) (например, 2() + 2() + 2() 3(, ) + 3(, )).

Допустим, удалось доказать это неравенство для любых трёх совместно рас­ пределённых случайных величин,, таких, что случайные величины и независимы при всяком известном исходе случайной величины. Тогда это неравенство истинно и для любых вообще совместно распределённых случай­ ных величин,,.

В самом деле, пусть даны произвольные совместно распределённые слу­ чайные величины,, с исходами в некоторых множествах,,, соот­ светственно. Обозначим через распределение случайной величины (, ) (с исходами в ), а через — распределение пары случайной величины (, ) (с исходами в ). Несложно убедиться, что существует полупрямое произведение распределений и (на множестве ), отно­ сительно которого с вероятностью 1 первая и третья координаты совпадают, а вторая и четвёртая координаты независимы при любой известной первой (= третьей) координате. Обозначим через,,, случайные величины, равные первой, второй, третьей и четвёртой координате четвёрки, выбранной случайно по распределению. Тогда и независимы при всяком извест­ ном исходе случайной величины, поэтому исходное неравенство выполнено для этой тройки случайных величин. С другой стороны, распределение пары (, ) такое же, как и у пары (, ). То же самое верно и для пары (, ) и для каждой из случайных величин,,. Поэтому шенноновская энтропия пары (, ) та же, что и у пары (, ), и то же самое верно для пары (, ) и для,, по отдельности. Следовательно, исходное неравенство верно и для данной (произвольной) тройки,,.

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

Пример 3. Из этого примера и возник вопрос, изученный во второй гла­ ве. Пусть = есть пространство всех сверхслов из нулей и единиц. Пусть есть бернуллиевская мера на с рациональным параметром 1, а есть бернуллиевская мера на с рациональным параметром 2 > 1. (Бернулли­ евская мера с параметром определяется, как распределение вероятностей на последовательностях, полученных в результате бесконечного числа неза­ висимых бросаний монетки, выдающей 1 с вероятностью и 0 с вероятностью 1.) Будем рассматривать бесконечные 0-1-последовательности, случайные по Мартин-Лёфу относительно распределения (определение случайности по Мартин-Лёфу можно найти, например, в [7]). В работе [9] доказано, что в лю­ бой такой последовательности можно заменить некоторые нули на единицы так, чтобы полученная последовательность была случайна по Мартин-Лёфу по распределению. Это доказывается с помощью рассмотрения вычислимо­ го полупрямого произведения распределений и, относительно которого с вероятностью 1 последовательность покомпонентно меньше последователь­ ности (несложно доказать, что у бернуллиевских распределений с вычисли­ мыми параметрами 2 > 1 такое полупрямое произведение в самом деле су­ ществует). Точнее, в [9] доказан следующий общий факт: если у вычислимых распределений и на пространстве бесконечных 0-1-последовательностей существует вычислимое полупрямое произведение, относительно которого с вероятностью 1 последовательность покомпонентно меньше последова­ тельности, то в любой бесконечной последовательности, случайной по Мар­ тин-Лёфу относительно распределения можно заменить некоторые нули на единицы так, чтобы полученная последовательность была случайна по Мар­ тин-Лёфу по распределению.

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

Основной результат главы Теорема 0.5. (опубликовано в [17]) Существуют две вычислимые меры и на N, которые имеют полупрямое произведение, согласованное с от­ ношением, но не имеют вычислимого полупрямого произведения, согласо­ ванного с отношением.

0.3. Транзитивность отношения Тоома на мерах на сверхсловах В третьей главе изучаются отношения на мерах на двусторонних сверх­ словах, в частности доказывается транзитивность отношения на мерах на дву­ сторонних сверхсловах в алфавите из двух символов, предложенного проф.

А.Л. Тоомом и позволяющего сравнить больше мер, чем стандартное продол­ жение на меры отношения на алфавите, рассмотренное во второй главе.

Данное отношение было введено с целью изучения вероятностных одно­ мерных клеточных автоматов с возможностью стирания и добавления кле­ ток.

Во второй главе мы рассматриваем отношение порядка на мерах на од­ носторонних сверхсловах. В третьей главе рассматриваются двусторонние сверхслова и меры на них, инвариантные относительно сдвига. Рассмотрен­ ный во второй главе способ продолжения на меры отношения порядка не позволяет нам, например, сравнить меры, сконцентрированные на сдвигах сверхслов... ( )... и... ( ).... При этом неформаль­ но можно сказать, что одна из мер получается из другой в каком-то смысле добавлением лишних плюсов. Рассматриваемое в третьей главе отношение было предложено А.Л. Тоомом для рассмотрения операторов, позволяющих вычёркивание. В частности, оно позволяет сказать, что вторая мера в новом смысле больше первой.

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

С середины XX века их также рассматривают и в качестве вычислительных моделей.

Вопрос сохранения вероятностным клеточным автоматом разницы меж­ ду двумя конфигурациями представляет интерес при разных подходах к изу­ чению клеточных автоматов. Этот вопрос может быть интерпретирован и как хранение информации в вычислительной системе с помехами, и как модели­ рование фазового перехода, и как изучение условий эргодичности с точки зрения теории динамических систем. Для двумерных клеточных автоматов сохраняющий информацию при помехах клеточный автомат был построен в работе [11]. В работе [12] приводится пример одномерного клеточного авто­ мата, в котором все вероятности перехода положительны и который способен надёжно сохранять один бит информации несмотря на помехи.

К сожалению, требуемая для этого конструкция оказывается очень слож­ ной. В связи с этим представляют интерес родственные задачи с более сла­ быми требованиями. В работе [13] построен достаточно простой пример од­ номерного клеточного автомата с возможностью стирания клеток, который сохраняет один бит информации несмотря на положительные вероятности почти всех переходов, и исследуются параметры фазового перехода между эргодичностью и неэргодичностью для этого автомата.

Неформально говоря, построенный клеточный автомат можно описать следующим образом. На ленте стоят плюсы и минусы, причём за шаг каждый минус может с некоторой вероятностью превратиться в плюс. После этого па­ ры соседних противоположных символов с некоторой (большей, чем вероят­ ность появления ошибки) вероятностью стираются. (При строгом определе­ ние этого оператора требуется указать, что происходит с нумерацией позиций сверхслова, когда в нём выполняется бесконечно много стираний. Строгое определение этого оператора требует определять его как действующий на мерах, инвариантных относительно сдвига.) Этот автомат, который мы назы­ ваем асимметричным автоматом Тоома, имеет следующее свойство. Если в начальный момент времени на ленте стоят одни минусы, то в любой момент времени с большой вероятностью в случайно выбранной клетке ленты будет стоять минус. (Мы упрощаем формулировку, точное утверждение будет да­ но позднее.) С другой стороны, если в начальный момент времени на ленте стоят одни плюсы, то в любой момент времени в любой клетке ленты будет стоять плюс. Это свойство и означает, что автомат способен сохранять один бит информации.

После этого возник вопрос, можно ли полученный результат перенести на случай двусторонней ошибки, то есть, на симметричный автомат Тоома.

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

Вопрос сохранения преобладания плюсов перестаёт быть тривиальным (под действием асимметричного оператора Тоома сверхслово из одних плюсов не изменяется никогда), но оказывается равносильным сохранению преоблада­ ния минусов. Однако стандартное отношение сравнения на мерах на двусто­ ронних сверхсловах не позволяет доказать монотонность рассматриваемых операторов из-за возможности стирания.

Для преодоления этой трудности А.Л. Тоом предложил рассмотреть дру­ гое отношение сравнения, определённое только на мерах, инвариантных отно­ сительно сдвига, и являющееся на них продолжением стандартного отноше­ ния порядка. Нестрого его можно описать так: мера больше меры, если из меры можно вычёркиванием плюсов, добавлением минусов и заменой плю­ сов на минусы получить меру. Разумеется, можно обратными операциями (вычёркивание минусов, добавление плюсов и заменой минусов на плюсы) получать из меры меру или пытаться получить одну и ту же меру из и вычёркиванием плюсов из и минусов из. В таких терминах стан­ дартное отношение порядка требует получить из одной меры другую только заменами плюсов на минусы.

В частности, данное отношение А.Л. Тоом упоминал и определял в курсе [14].

ющими свойствами:

1. Отношение транзитивно.

2. асим сим, где сим, асим обозначают, соответственно симметричный и асимметричный операторы Тоома.

3. Если, то -вероятность плюса в данной клетке больше или равна -вероятности плюса в данной клетке.

4. Хотя бы один из двух операторов Тоома обладает следующим свойством Действительно, пусть эти условия выполняются. Обозначим исходную меру, сосредоточенную на двустороннем сверхслове из одних минусов, 0.

Предположим для примера, что симметричный оператор Тоома монотонен.

Тогда рассмотрим результаты -кратных итераций по индукции. База оче­ видна: асим (0 ) = сим (0 ) = 0. Далее, по второму и четвёртому свойству (монотонность и предположение индукции) По первому свойству такую цепочку неравенств можно заменить на од­ но неравенство, откуда следует асим (0 ) сим (0 ). Требуемое утверждение после этого следует из теоремы для ассимметричного оператора и третьего свойства (отношение между мерами гарантирует отношение между рассмат­ риваемыми вероятностями).

Достаточность этих условий будет более аккуратно доказана в третьей главе.

Однако А.Л. Тоому не удалось доказать транзитивность такого отноше­ ния на мерах, его транзитивность осталась открытым вопросом. Это не поз­ воляло использовать его для доказательство возможности сохранения одного бита информации в автомате Тоома с двусторонней ошибкой (= симметрич­ ном автомате Тоома). В третьей главе доказывается транзитивность этого отношения и монотонность оператора вычёркивания части пар относительно этого отношения (опубликовано в [18]).

Второе и третье свойство будут следовать непосредственно из точных определений рассматриваемых отношения и оператора. Транзитивность, до­ казываемая в диссертации, является первым свойством. Кроме того, в дис­ сертации доказана монотонность оператора Duel относительно рассматрива­ емого отношения.

Для доказательства гипотезы Тоома о неэргодичности симметричного оператора с помощью соображений монотонности и рассмотренного отноше­ ния порядка остаётся доказать монотонность хотя бы одного из операторов внесения ошибок (симметричного или асимметричного) относительно такого отношения, другими словами, проверить четвёртое свойство отношения. Этот вопрос остаётся открытым.

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

Автор благодарен академику РАН А.Л. Семёнову, к.ф.-м.н. доценту М.Н.

Вялому, к.ф.-м.н. А. Шеню и профессору А. Л. Тоому за постановку вопро­ сов, рассмотренных в диссертации.

Автор благодарит всех участников Колмогоровского семинара, а особен­ но к.ф.-м.н. Ю.Л. Притыкина, к.ф.-м.н. А.Ю. Румянцева и PhD Л. Бьянвеню за обсуждения, как связанные, так и не связанные непосредственно с темой диссертации.

Действие конечного автомата на почти 1.1. Поведение регулятора почти периодичности Непосредственно из определения 0.2 следует, что регулятор почти пе­ риодичности — монотонно неубывающая функция. Действительно, каждое слово, входящее в сверхслово, можно продолжить до слова любой большей длины, также входящего в заданное сверхслово. Вхождения продолжения бу­ дут содержать вхождения более короткого слова.

Ясно, что регулятор почти периодичности не может принимать на ка­ ком-то аргументе значение меньше этого аргумента. Для периодической по­ следовательности с периодом значение регулятора почти периодичности на входе не превышает + 1, как замечено выше.

Впрочем, регулятор почти периодичности может расти и намного быст­ рее. В этой главе, например, для любой заданной функции приводится при­ мер сверхслова, у которого регулятор почти периодичности бесконечное чис­ ло раз превышает выбранную функцию.

1.2. Почти периодические сверхслова и конечные автоматы В [3, 4] фактически получена верхняя оценка регулятора конечно-авто­ матного образа через регулятор исходного сверхслова. Но эта оценка очень быстро растет.

Напомним формулировку теоремы 0.1.

Будем обозначать через (·) функцию, являющуюся -кратной компо­ зицией функции (·) с собой: () = ( (... ( )... )).

Теорема. (0.1) [[3, 4]] Если у заключительно почти периодического сверх­ слова регулятор не превосходит () 1 и автомат имеет состояний, то у его образа под действием автомата регулятор не превосходит ().

Эта же оценка имеет место для регулятора прямого произведения за­ ключительно почти периодического сверхслова и периодического сверхслова с периодом.

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

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

Это утверждение верно, но оно не гарантирует, что значения регулятора почти периодичности прямого произведения существенно больше значений регулятора почти периодичности исходного сверхслова на многих аргумен­ тах. Действительно, регулятор почти периодичности может быть медленно растущей функцией. Например, для последовательности из одних нулей ре­ гулятор почти периодичности равен тождественной функции. Если регулятор почти периодичности исходного слова является тождественной функцией, то указанная формулировка гарантирует всего лишь, что регулятор произве­ дения сверхслова и некоторого периодического сверхслова с периодом принимает на значение, большее +.

Поэтому в формулировку необходимо добавить условие, гарантирующее, что регулятор почти периодичности прямого произведения существенно боль­ ше регулятора почти периодичности исходного сверхслова, даже если послед­ ний растёт медленно. Например, можно потребовать, чтобы он был больше, чем max{, } (), где — любая наперед заданная возрастающая функ­ ция. Условие, что регулятор быстро растёт, можно сформулировать по-разно­ му. Докажем сначала, что сформулированное неравенство выполняется для бесконечно многих длин.

Напомним формулировку теоремы 0.2.

Теорема. (0.2) Если задана возрастающая функция натурального аргумен­ та, то существует почти периодическое сверхслово нулей и единиц со следующими свойством. Для всех > 100 и бесконечно многих значение на регулятора обобщённой почти периодичности сверхслова Cycle пре­ вышает (max{, }+1) 30 (), где Cycle обозначает сверхслово ( mod ), а — регулятор почти периодичности сверхслова.

Эта теорема показывает, что в теореме 0.1 количество итераций функции должно расти линейно с ростом.

1.4. Конструкция требуемого сверхслова Мы определим сверхслово вместе с числовой последовательностью, так что 2) для регулятора сверхслова выполнено неравенство +1 > ( );

3) для > > 100 значение на регулятора почти периодичности сверхслова Cycle превышает +.

Сначала убедимся, что этого будет достаточно для доказательства теоре­ мы. Из первого и второго свойств следует, что + (max{, }+1) ( ).

Подставив в это неравенство = 30 и применив третье свойство последова­ тельности и сверхслова, мы получим утверждение теоремы для = и произвольного >.

Рассмотрим следующие слова из нулей единиц:

В этих формулах 1, 2,... — некоторая последовательность натуральных чисел.

Для дальнейшего нам важны следующие свойства слов,, :

длины слов 0, 0, 0 образуют арифметическую прогрессию с разно­ стью 1, и то же самое верно для всех (чуть ниже мы докажем это), любое вхождение любого из слов 0, 0, 0 в любое слово, составленное из блоков 0, 0, 0, является целым блоком (чуть позже мы уточним, что это значит, и докажем это), слова +1, +1, +1 начинаются с достаточно большого количества вхождений слова (самого короткого из слов,, ), в каждое из слов +2, +2, +2 входят все 9 возможных пар блоков При этом мы выбрали более длинные слова 0, 0, 0, чем это необхо­ димо, чтобы упростить вычисления.

Так как для всех слово является префиксом +1, существует сверх­ слово, содержащее все в качестве префиксов. Оно и будет искомым сверхсловом. Последовательности 1, 2,... и 1, 2,... мы зафиксиру­ ем позднее. А сейчас установим некоторые свойства построенного сверхслова 1.5. Базовые свойства конструкции Определение 1.1. Каждое слово с индексом (, или ) определено как конкатенация копий слов с индексом 1. Разворачивая рекуррентное соотношение, это слово можно представить как конкатенацию копий слов с индексами 2, копий слов с индексами 3 и так далее. Вхождения копий слов с некоторым индексом в слово с бльшим индексом, которое можно найти с помощью этого представления, назовем корректными.

корректны.

Доказательство. Утверждение почти очевидно из-за наличия уникаль­ ных фрагментов в словах каждого уровня. Доказательство проведем индук­ цией по.

База: слова с индексом 0 могут входить только корректно. В самом де­ ле, каждое слово с индексом нуль начинается с последовательности 100. Эта последовательность не является подсловом никакого слова с индексом нуль (за исключением начала) и не может быть представлена как конкатенация некоторого непустого конца слова с индексом нуль и некоторого начала слова с индексом нуль (это легко проверяется, глядя на слова 0, 0, 0 ). Поэтому любое вхождение слова с индексом нуль в, или начинается с неко­ торой позиции, с которой начинается некоторое корректное вхождение (воз­ можно другого слова). С другой стороны, ни одно из слов индекса нуль не является началом никакого другого. Следовательно, любое вхождение слова с индексом нуль в, или корректно. База индукции доказана.

Индуктивный переход: по предположению индукции любое вхождение слова с индексом + 1 должно состоять из корректных вхождений слов с ин­ дексом. Если считать блоки, составляющие слова с индексом + 1, отдельными буквами, то слова с индексом + 1 имеют те же свойства, которые были использованы в базе индукции. А именно, каждое из слов ин­ декса +1 начинается со слова, которое не является подсловом никакого слова с индексом + 1 (за исключением начала) и не может быть представлено как конкатенация некоторого непустого конца слова с индексом +1 и некоторого начала слова с индексом +1. Кроме того, никакое слово с индексом +1 не является началом другого слова с индексом +1. Лемма 1.1 доказана.

Лемма 1.2. Длина слова вычисляется по формуле | | = = 10+ Доказательство. Проверим это по индукции. При = 0 утверждение очевидно.

Индуктивный переход: +1 является конкатенацией 10+1 8 слов дли­ ны 10+ на единицу больше. В сумме получаем как раз в 10+1 раз больше, чем на предыдущем шаге, что и требовалось.

Слова +1 и +1 отличаются от +1 только заменой одного слова в кон­ катенации на слово, которое на один символ короче или длиннее соответствен­ но.

1.6. Позиции вхождений слов в сверхслово и их остатки Нам нужно показать, что регулятор сверхслова относительно малень­ кий, а регулятор сверхслова Cycle — большой. Точнее, нам нужно оценить сверху или снизу значения этих функций на числе, которое мы можем выбрать по своему усмотрению. Мы выберем в качестве длину слова 3, равную 3. Таким образом, нам нужно будет показать две ве­ щи: регулятор сверхслова принимает на 3 значение, меньшее 3+3, а регулятор сверхслова Cycle — большее 3+/10.

Мы начнём со второго. Чтобы установить это, нужно предъявить слово длины не больше 3, которое встречается в Cycle бесконечно много раз, но расстояния между соседними вхождениями велики. Мы будем счи­ тать, что слово Cycle записано в алфавите остатков от деления на (напри­ мер, 1 и 1 являются обозначениями одного и того же символа). Таким словом будет произведение слова 3 и слова Чтобы доказать, что оно встречается в Cycle достаточно редко, нам нужно понять, с каких позиций могут начинаться вхождения слова 3 в слово, и показать, что номера таких позиций, сравнимые с /2 по модулю, встречаются достаточно редко.

Лемма 1.3. В любом слове с индексом + слово входит, начиная с позиций, дающих все остатки от до 0 по модулю (и, возможно, другие). При этом никакое слово с индексом (то есть,, ) не входит ни в какое слово с индексом + начиная с позиций с остатками по модулю, не лежащими от 4 до 0 (данное утверждение нетривиально только при > 4).

Доказательство. Докажем индукцией по. База = 1 почти очевид­ на: с одной стороны первое и второе вхождения в слова с индексом + дают остатки 0 и 1. С другой стороны, мы знаем, что все вхождения слов с индексом в слова с индексом + 1 корректны. И можно непосредственно убедиться, что номера позиций начал корректных вхождений слов с индексом в слова с индексом + 1 суть 0, 1, 2, 3, 4 по модулю.

Пусть для = это верно. Рассмотрим теперь = + 1, и пусть дано любое слово с индексом + + 1. Сначала докажем первое утверждение. По предположению индукции в данном слове есть вхождение +1 на позиции с остатком по модулю +1, а значит, и по модулю, так как +1..

Это вхождение +1 начинается со вхождения ; так мы получим вхождение с остатком по модулю. Аналогичным образом доказывается суще­ ствование вхождений с остатками от + 1 до 0 по модулю. Остаток 1 даст второе вхождение во вхождение +1, начинающееся с позиции с остатком по модулю.

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

Остатки от деления на позиций вхождений слов с индексом в слово с индексом + 1 относительно его начала лежат от 4 до 0, а само начало по предположению индукции имеет позицию с остатком от 4 до 0 при делении на. Складывая остатки, получаем второе утверждение леммы.

1.7. Нижняя оценка на регулятор почти периодичности прямого произведения построенного сверхслова и периодического сверхслова Лемма 1.4. Пусть. и > > 100. Тогда регулятор почти периодич­ ности сверхслова Cycle на принимает значение большее +.

Более того, регулятор любого суффикса Cycle обладает этим свой­ ством.

позиции на можно считать как остаток от деления на остатка от деления Рассмотрим произвольное > +. По лемме 1.3 в слове есть вхождения, начинающиеся с позиций, дающих все возможные остатки от деления на, так как разность не меньше. В частности, там есть и вхождение с остатком /2 по модулю. Заметим, что содержит бес­ конечно много непересекающихся вхождений. Поэтому любой суффикс сверхслова Cycle содержит вхождение прямого произведения слова и слова (имеется в виду, что мы продолжаем эту последовательность с периодом, пока её длина не станет равной длине слова ).

Чтобы завершить доказательство первого утверждения леммы 1.4, по­ кажем, что некоторое подслово длины + в Cycle не содержит вхождений рассматриваемого произведения. Таким подсловом будет, напри­ мер, начало этого слова длины +. Действительно, нетрудно убедиться, что при > 100 выполнено неравенство |+ | > +. Поэтому рас­ сматриваемое начало является префиксом прямого произведения сверхсло­ ва + и начала сверхслова Cycle подходящей длины. По лемме 1.3 сло­ во + может содержать только вхождения, начинающиеся с позиций 4 9,..., 0 по модулю. Поскольку 4 < /2, среди этих остатков отсутствует /2.

Для доказательства второго утверждения леммы 1.4 осталось заметить, что слово содержит бесконечно много вхождений слова +, начинаю­ щихся в позициях, кратных (опять же по лемме 1.3).

1.8. Верхняя оценка регулятора построенного сверхслова Лемма 1.4 устанавливает нужную нижнюю оценку регулятора почти пе­ риодичности сверхслова Cycle. Осталось получить верхнюю оценку ре­ гулятора почти периодичности самого сверхслова. Здесь мы будем исполь­ зовать то обстоятельство, что слова с индексом + 2 содержат все возможные пары слов с индексом.

Лемма 1.5. Любое слово, которое является подсловом конкатенации двух слов с индексом, входит в каждое слово с индексом + 2.

Доказательство. Любая комбинация рядом стоящих слов с индексом встречается хотя бы в одном из слов уровня +1. В каждом из слов +2, + и +2 встречается каждое из слов предыдущего уровня, что и требовалось.

Заметим, что усложнив немного конструкцию слов, и, можно сделать, чтобы доказанная лемма была справедлива для +1 вместо +2. Мы не делаем этого, поскольку не стремимся (пока) к уменьшению константы в формулировке теоремы 0.2. Как мы увидим ниже, при более аккуратной формулировке и при немного другом условии на нижнюю оценку роста регу­ лятора константа 30 может быть уменьшена почти до 1. Что означает “почти” мы уточним позже.

Лемма 1.6. Сверхслово почти периодическое и регулятор его почти периодичности можно оценить следующим образом:

Доказательство. Первое неравенство: левая половина слова +1 не содержит, хотя все слово +1 содержит и встречается в сверхслове бесконечно много раз.

Второе неравенство: любой участок длины 2+2 + 1 содержит целиком хотя бы одно слово уровня +2. Такое слово, как уже доказано, содержит лю­ бое слово, которое можно покрыть двумя непересекающимися словами с ин­ дексом (а участок длины не может пересекаться сразу с тремя вхожде­ ниями слов с индексом ).

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

1.9. Завершение доказательства Закончим построение искомых сверхслова и последовательности.

Пусть задана функция. Построим последовательность 1, 2,... по форму­ лам 1 = 3 (1), +1 = 3( + 1) ( ). В качестве возьмем = 3.

Проверим выполнение условий теоремы: +1 = 3+3 > 3+1 > (3 ) = ( ), регулятор последовательности почти периодичности сверхслова на принимает значение меньшее +1, а при > регулятор последова­ тельности Cycle на принимает значение, превосходящее 3+ +, что и требовалось.

Замечание. Как видно из приведённых оценок, регулятор сверхслова принимает на значение, большее ( ). Поэтому возникает искуше­ max{, } на. Этого нельзя делать, поскольку мы не доказали, что нера­ венство имеет место для всех аргументов.

1.10. Улучшение нижней оценки теоремы 0. В приведённой конструкции и доказательстве имеется большой запас и константу 30 можно понизить, существенно не меняя конструкции.

В этом разделе, в качестве примера усиления оценки, будет доказана теорема 0.3.

Теорема 1.1. Пусть задана возрастающая функция : N N. Тогда най­ дётся почти периодическое сверхслово с регулятором почти периодично­ сти и следующими свойствами.

1) Для бесконечного количества аргументов превышает. Более того, эти аргументы выстроены в цепочку: существует последователь­ ность натуральных чисел, такая что 2) Для любого > 2 и любого регулятор почти периодичности Cycle удовлетворяет неравенствам Cycle ( ) > + 3) Для любого достаточно большого регулятор почти периодично­ сти всё того же прямого произведения Cycle на всех достаточно больших значениях аргументов превышает 3.

Доказательство. Для доказательства изменим немного конструкцию слов,,. Слова 0, 0, 0 менять не будем, а +1, +1, +1 определим по-другому:

Из определения видно, что для любого длины слов,, отлича­ ются на 1: как и раньше, обозначим длину через, тогда длина есть 1, а длина есть + 1. Последовательность 1, 2,... подберём из того расчёта, чтобы для всех при всех достаточно больших число было кратно и чтобы +1 было больше 100 ( ). Кроме того, сделаем > 100.

Слова +1, +1, +1 выбраны такими, чтобы:

(а) каждое из них содержало пары,,, и в любой своей четверти и конкатенация любых слов из +1, +1, +1 не содержала других пар из слов,, ;

(б) в каждом из них был фрагмент длины не менее одной шестой от всего слова, не содержащий.

(в) в любом начале любого из слов +1, +1, +1 разница между количе­ ством и количеством принимала оба значения 0 и 1 не менее одного раза и не принимала никаких других значений;

(г) в каждом из них ровно в одном месте входят + 2 копии подряд.

Из-за наличия уникального фрагмента +2 в одном и том же месте каждого из слов уровня + 1 и того, что слова уровня + 1 не продолжают,, в,, корректны. Из свойства (в) следует такой аналог леммы 1.3:

Лемма 1.7. В любом слове с индексом + любое слово с индексом вхо­ дит начиная с позиций, дающих только остатки от до 0 по модулю, причём для каждого такого остатка и любого слова уровня + неко­ торое слово с индексом входит в это слово, начиная с позиции, дающей этот остаток. Слово входит во все слова с индексом + начиная с по­ зиций, дающих только остатки от до 0 по модулю и все остатки реализуются (в любом слове с индексом + ).

Из этой леммы следует оценка на регулятор прямого произведения сверхслова и Cycle : а именно, выполнено неравенство (для всех, для которых кратно ). В самом деле, рассмотрим прямое произведение слова и слова Это слово входит в Cycle. Действительно, рассмотрим любое число, удовлетворяющее неравенству Тогда входит в +, начиная с некоторой позиции, сравнимой с + по модулю.

С другой стороны, верно и обратное — если слово входит в начало + начиная с некоторой позиции, сравнимой с + 1 по модулю, то удовлетворяет этому неравенству. Таким образом, мы нашли слово длины, не входящее в некоторые подслова длины +2. При этом оно входит в наше сверхслово бесконечно много раз. Таким образом, значение регулятора на больше +2.

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

Теперь установим, что Слово длины 1 не встречается между своими двумя вхождениями в два соседних повтора пятикратно повторяемого блока в середине слова уровня + 1, что позволяет указать подслово длины +1 /6 без вхождений данного слова длины 1.

Вспоминая, что ( ) < 6 +1, мы можем заключить, что для регулято­ ра сверхслова выполняются неравенства при всех значениях. Поскольку регулятор не убывает, индукцией по лег­ ко доказывается, что ( ) +2, что, напомним, меньше Cycle ( ).

Теперь рассмотрим произвольную длину < < +1. Заметим, что Таким образом, теорема 0.3 доказана полностью.

Можно посмотреть на конструкцию при конкретном выборе. Длина слова равна 10 5 ( + 6). Пусть, скажем, +1 = | |. Тогда на некоторой подпоследовательности длин регулятор ведёт себя как (2 ), а регулятор Cycle как (2 ).

Полупрямые произведения вычислимых мер на 2.1. Основные свойства полупрямых произведений, согласованных с отношением В качестве примера использования определения 0.6 докажем сначала наличие полупрямого произведения, согласованного с отношением, для двух конкретных мер. Рассмотрим меру, сконцентрированную на последователь­ ности с периодом и меру, сконцентрированную на последовательности с периодом Ясно, что. Действительно, мера, сконцентрированная на последова­ тельности с периодом приписывает нулевую вероятность слову, отсутствие в сверхслове вхожде­ ний этого слова обеспечивает выполнение нестрогого покомпонентного нера­ венства между проекциями и имеет проекции, равные рассматриваемым ме­ рам.

Как уже было упомянуто во введении, из теоремы Форда–Фалкерсона [8] о максимальном потоке и минимальном разрезе следует простой критерий того, что распределение находится в отношении с. Авторство данного критерия достоверно неизвестно.

Напомним формулировку теоремы 0.4.

Теорема. (0.4) Распределение находится в отношении с, тогда и только тогда, когда не существует подмножеств,, таких что все -соседи лежат в и () > ().

Для полноты изложения приведём доказательство этого критерия. Яс­ но, что если распределение находится в отношении с, то таких под­ множеств нет. В самом деле, рассмотрим полупрямое произведение, для которого ( ) = 1. Предположим, что все -соседи лежат в. Тогда Второе равенство здесь выполнено, поскольку носитель распределения вклю­ чен в, а третье — поскольку все -соседи лежат в.

Теперь докажем обратное утверждение. Для этого рассмотрим следую­ щую сеть (рис. 2.1). Из источника выходит || рёбер, они ведут в вершины, Рис. 2.1. Пример сети, соответствующей заданному отношению.

соответствующие элементам. Их пропускные способности равны значени­ ям на соответствующих элементах. Рёбра, ведущие в сток, выходят из вершин, соответствующих элементам, а их пропускные способности равны значениям. Ребра сети между вершинами и соответствуют элемен­ там бинарного отношения — их пропускные способности не ограничены.

По построению, в этой сети можно пропустить поток мощности 1 из истока в сток тогда и только тогда, когда существует полупрямое произведение, для которого ( ) = 1: значение на паре (, ) соответствует количеству жидкости, проходящей из в, наличие в сети рёбер только из ограничи­ вает носитель распределения отношением. Теорема Форда–Фалкерсона утверждает, что для произвольной сети, если из источника в сток невозмож­ но пропустить поток мощности, то к этому есть следующее препятствие:

все вершины сети можно разделить на два множества, (разрез) так, что­ бы исток попал в, сток попал в, и сумма пропускных способностей всех рёбер сети, ведущих из в, (величина разреза) была меньше. В нашем случае множество, существующее по этой теореме, вместе с любой своей вершиной должно содержать и всех её соседей (иначе величина разреза бу­ дет неограниченной). Возьмем в качестве множество всех вершин из, лежащих в, а в качестве — множество всех вершин из, лежащих в.

Величина разреза равна (1())+() (первое слагаемое равно сумме про­ пускных способностей ребер из источника в, а второе — сумме пропускных способностей ребер из в сток). Поскольку эта сумма меньше 1, мы можем заключить, что () > ().

В определении 0.7 упоминалось, что для вычислимости распределения на N достаточно существования вероятностного алгоритма (алгоритма, име­ ющего доступ к независимым бросаниям симметричной монеты) без входа, который на выходной ленте печатает случайную бесконечную последователь­ ность с распределением.

В самом деле, для оценки с точностью -меры множества всех про­ должений слова, запустим алгоритм порождения распределения и будем пробовать всевозможные результаты бросаний и смотреть, на каких из них алгоритм напечатает целиком (и возможно, что-то еще). Таким образом мы сможем приближать ( ) снизу и наши приближения будут сходиться к ( ). Правда, мы не знаем, в какой момент у нас уже имеется приближение с точностью. Для этого надо вычислять приближения снизу также и для всех остальных слов той же длины, что и. Когда сумма всех этих прибли­ жений снизу станет больше 1, мы будем уверены, что точность каждого из них не хуже. Аналогичное верно и для вероятностных мер на N N.

2.2. Основной результат.

В этом разделе мы предъявим две вычислимые вероятностные меры на пространстве бесконечных 0-1-последовательностей, которые имеют полупря­ мое произведение, согласованное с отношением покомпонентного порядка, но все такие полупрямые произведения невычислимы.

Напомним формулировку теоремы 0.5.

Теорема. (0.5) Существуют две вычислимые меры и на {0, 1}N, кото­ имеют вычислимого полупрямого произведения, согласованного с отноше­ Доказательство. Вначале рассмотрим случай, когда в качестве взя­ то не множество {0, 1}, а более сложно устроенное конечное частично упо­ рядоченное множество. Оно будет содержать шесть элементов, называемых,,,,, с частичным порядком: <, <, <, < (см. Рис. 2.2).

Сначала рассмотрим следующие два распределения на последовательно­ стях из букв,,,. Пусть 0, 1, 2,... независимы и принимают значения и с вероятностью 1/2. Аналогичным образом пусть 0, 1, 2,... независи­ мы и принимают значения и с вероятностью 1/2. У случайных величин = 0 1 2... и = 0 1 2... есть много различных полупрямых произведе­ ний. Можно считать, например, что = при = и = при = ;

можно поменять и местами; наконец, можно считать и независимыми.

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

Распределения на и будут играть в наших рассуждениях вспомога­ тельную роль. А именно, для распределений и, которые мы построим, так будут распределены буквы на чётных позициях. Точнее, обозначим через случайную относительно последовательность, а через случайную относи­ тельно последовательность. Тогда 2 принимает значения, с равными вероятностями 1/2 (для всех ), и при разных эти события независимы.

Аналогично 2 принимает значения, с равными вероятностями 1/2, и при разных эти события независимы.

Для того, чтобы определить распределения букв сверхслов и на нечётных позициях, нам понадобится пара, перечислимых неотделимых множеств натуральных чисел (см., например, [15]). Напомним, что это озна­ чает, что и перечислимы, не пересекаются и не существует алгоритма, ко­ торый, получив на вход любое натуральное число, выдаёт 0 или 1, причем, если, то он обязательно выдаёт 0, если, то он обязательно выдаёт 1. Такой алгоритм (когда он существует) называется отделителем множеств,. Перечислимость множества означает, что существует вычислимая по­ следовательность натуральных чисел, множество значений которой равно (в этом случае говорят, что последовательность перечисляет ). Поскольку перечислимые неотделимые множества обязаны быть бесконечными, можно без ограничения общности считать, что последовательность, перечисляющая, состоит из различных чисел, то есть, перечисляет без повторений (и то же самое для ). В построении мер на и мы будем использовать по­ следовательность, полученную соединением этих двух последовательностей.

А именно, мы рассмотрим последовательность 0, 1, 2, 3,... такую, что по­ следовательность чётных членов 0, 2,... перечисляет без повторений мно­ жество, а последовательность нечётных членов 1, 3,... перечисляет без повторений множество.

Нечётные члены последовательности определяется через её четные члены следующим детерминированным правилом:

Напомним, что 2 выбирается случайно среди букв, с равномерным распределением. Таким образом, первое распределение полностью задано.

Нетрудно убедиться, что оно вычислимо. В самом деле, чтобы вычислить ме­ ру множества всех продолжений слова нужно сделать следующее: если в слове есть буквы, отличные от,,,, то мера равна нулю. Иначе, для каждой нечётной позиции 2 + 1 в вычислим. Если для хотя бы одного такого позиция 2 входит в, но пара букв слова, стоящих в позициях 2 + 1, 2, отлична от пар (, ) и (, ), то опять же мера равна нулю. А иначе мера равна 2, где обозначает количество свободных позиций в — так мы называем все чётные позиции, а также все нечётные позиции 2 + 1, для которых позиция 2 не входит в.

Нечётные члены последовательности определяется похожим (также детерминированным) правилом. Только на этот раз нам важна еще чётность (напомним, что от этого зависит, какому из двух множеств, принадле­ жит ). Для чётных :

а для нечётных — всё наоборот:

Распределение вероятностей теперь тоже полностью определено. Его вы­ числимость доказывается так же, как и вычислимость распределения.

Осталось понять, почему у распределений, есть полупрямое распре­ деление, согласованное с покомпонентным частичным порядком, но нет та­ кого вычислимого полупрямого произведения. Сначала докажем существова­ ние. В качестве полупрямого произведения распределений, можно взять распределение, порождаемое следующим процессом:

Для всех натуральных чисел (независимо друг от друга):

если =, то выбираем с равными вероятностями 1/2 один из следующих двух случаев:

если =, то выбираем с равными вероятностями 1/2 один из следующих двух случаев:

наконец, если не лежит ни в, ни в, то порождаем только па­ ру букв 2, 2 в соответствии с первой или второй из матриц (2.1) (можно использовать и любую их выпуклую комбинацию, напри­ мер, третью матрицу).

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

Нетрудно также проверить, что его проекции равны,. В самом деле, с точки зрения последовательности случаи (а) и (в) одинаковы, так же как и случаи (б) и (г) и мы с вероятностью 1/2 выбираем одно из двух решений 1/2 выбираем одно из двух решений 2 = и 2 = при, не лежащем в объединении и, в полном соответствии с тем, как и положено делать по распределению. С точки зрения последовательности все случаи уже различны. При = и чётном мы с вероятностью 1/2 выбираем одно из двух решений 2+1 =, 2 = или 2+1 =, 2 =, как и диктует распределение. Аналогичное происходит и для = и нечётном и при, не лежащем в объединении и.

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

Более того, достаточно иметь и любой отделитель множеств,. В этом случае вероятностный алгоритм, порождающий распределение таков: па­ раллельно для всех мы запускаем отделитель на входе и порождаем пару 2, 2, выбрав для этого первую или вторую матрицу из (2.1) в соответствии с тем, что выдал отделитель на входе. После этого мы начинаем искать то, для которого =. Такого может не быть, в этом случае процесс поис­ ка для данного никогда не остановится, не принеся никакого вреда. Но если такое существует, то рано или поздно мы его найдём и сможем определить 2 в соответствии с уже выбранным значением 2, 2. По замечанию перед формулировкой теоремы из существования порождающего распределение алгоритма следует существование и вычисляющего алгоритма.

Можно вычислять меру, задаваемую данным отделителем, и непосред­ ственно. Пусть нам, скажем, надо найти вероятность того, что по мере последовательность продолжает данное слово, а последовательность продолжает данное слово. Тогда мы для всех чётных позиций 2, которые есть в или, применяем отделитель к. Затем мы смотрим, нет ли среди позиций, имеющихся в или, такой позиции 2 + 1, для которой =.

Если буквы в и в позициях 2, 2 + 1 не согласованы с выходом отдели­ теля (согласованность означает случаи (a) или (б), если отделитель выдал 0, и случаи (в) или (г), если он выдал 1; отсутствие указанной позиции 2 + в словах или не мешает согласованности), то вероятность равна нулю.

Иначе она равна 2, где обозначает количество свободных позиций в, — так мы называем все чётные позиции, которые присутствуют хотя бы в одном из слов, и все нечётные позиции 2 + 1, для которых позиция 2 не входит ни в, ни в.

Но нам нужно сделать обратное: из алгоритма, вычисляющего любое полупрямое произведение мер,, согласованное с покомпонентным по­ рядком, надо изготовить отделитель множеств,. Для этого разберёмся, каким должно быть любое полупрямое произведение мер,, согласован­ ное с покомпонентным порядком. Ключевую роль, здесь играет следующая лемма.

Лемма 2.1. Для любого чётного для = вероятность каждого из со­ бытий (а) и (б) выше равна в точности 1/2. Аналогично, для любого нечёт­ ного для = вероятность каждого из событий (в) и (г) выше точно­ сти равна 1/2.

Доказательство. Докажем первое утверждение (второе доказывается совершенно аналогично). Фиксируем чётное и =. Во-первых, с еди­ ничной вероятностью выполнено 2+1 = 2+1. В самом деле, относительно распределений, с вероятностью 1 на нечётных позициях в и могут быть только и, а они не сравнимы между собой. Теперь воспользуемся детерми­ нированной связью между 2+1 и 2. С половинной вероятностью 2 =, а значит 2+1 =, следовательно 2+1 =, а значит 2 = (последнее сле­ дует из детерминированной связью между 2+1 и 2 ). С оставшейся поло­ винной вероятностью выполнено 2 =, следовательно, 2+1 = 2+1 = Теперь мы можем доказать, что из любого алгоритма, вычисляющего некоторое полупрямое произведение мер,, согласованное с покомпонент­ ным порядком, можно изготовить отделитель множеств,. Для этого заме­ тим, что если, то по лемме вероятность события 2 =, 2 = равна 0 (поскольку = и = ), а если, то опять же по лемме эта веро­ ятность равна 1/2. Руководствуясь этим, на входе отделитель с точностью 1/4 вычисляет вероятность события 2 =, 2 =. и выдаёт 0, если прибли­ жённое значение меньше 1/4, и 1, иначе. Таким образом, из существования вычислимого полупрямого произведения следует существование отделителя и, что противоречит предположению об их неотделимости.

Осталось перейти от построенного нами шестиэлементного множества к последовательностям нулей и единиц. Это легко сделать, вложив в пятимерный булев куб с покоординатными сравнениями, например, так:

(вместо каждой буквы мы пишем пять битов). Можно также обойтись и бу­ левым квадратом:

Это вложение не даёт в точности того порядка, как на Рис. 2.2. Но можно заметить, что в доказательстве были использовано только то, что =, =, каждое из, меньше или равно каждого из, и несравнимость,.

Указанное вложение эти свойства сохраняет. Теорема доказана.

Меры на сверхсловах и клеточные автоматы 3.1. Постановка задачи В своих работах А.Л. Тоом рассматривал следующие операторы на ме­ рах.

Пусть заданы действительные числа, от 0 до 1. Рассмотрим следу­ ющие три оператора на инвариантных мерах (через них мы и определим операторы Тоома).

Flip+ превращает каждый символ в независимо с вероятностью Flip превращает каждый символ в противоположный независимо с ве­ Ann выделяет в сверхслове все вхождения и вычеркивает каждое из них (независимо от прочих) с вероятностью.

Каждый из этих операторов для любого исходного сверхслова задает некоторое распределение вероятностей на выходных сверхсловах. Чтобы при­ менить их к произвольной мере, надо усреднить эти распределения по данной мере на.

Симметричный оператор Тоома сим задается как композиция Flip и Ann (в указанной последовательности), а асимметричный оператор асим — как композиция Flip+ и Ann.

На самом деле, это описание не определяет оператор Ann. Более точное определение будет дано ниже.

В работе [13] сформулировано следующее предположение.

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

Для каждого момента времени вероятность того, что в этот момент данная компонента находится в состоянии, меньше.

Очевидно, что эта гипотеза эквивалентна симметричной гипотезе, полу­ чающейся из нее заменой.

Теорема 3.1 ([13]). Гипотеза 1 верна для асимметричного оператора Тоо­ ма. Точнее, для всех, и всех моментов времени вероятность плюса в данной клетке не превосходит 300/2.

Напомним свойства 0.3 отношения сравнения мер, нужные нам для доказательства гипотезы.

1. Отношение транзитивно.

2. асим сим, где сим, асим обозначают, соответственно симметричный и асимметричный операторы Тоома.

3. Если, то -вероятность плюса в данной клетке больше или равна -вероятности плюса в данной клетке.

4. Хотя бы один из двух операторов Тоома обладает следующим свойством монотонности:

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

Лемма 3.1. Если существует отношение на инвариантных мерах, удо­ влетворяющее перечисленным свойствам, то из утверждения теоремы 3. следует гипотеза 1.

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

База индукции: для = 1 это верно по второму свойству.

условию хотя бы один из двух операторов монотонен, пусть это будет, ска­ жем первый оператор. Тогда по монотонности +1 = сим ( ) сим ( ). С другой стороны по второму свойству сим ( ) асим ( ) = +1. По транзи­ тивности (первое условие) получаем +1 +1.

Из доказанного и третьего свойства следует, что для любого момента времени -вероятность плюса не меньше -вероятности плюса. Поэтому из теоремы 3.1 следует гипотеза 1. Лемма доказана.

В качестве кандидата на подходящее отношение А.Л. Тоом выдвинул ниже). Первое из них удовлетворяет первому и третьему свойствам, но, как мы показываем в настоящей работе, не удовлетворяет четвертому свойству.

влетворяет второму и третьему условиям. А вот транзитивность была сфор­ мулирована в качестве гипотезы и оставалась недоказанной. Доказательство этого факта и составляет основной результат настоящей главы. Выполнено ли четвертое свойство, в настоящий момент неизвестно. Если удастся его до­ казать, то гипотеза Тоома будет доказана.

3.2. Используемые базовые понятия и обозначения Определение 3.1. Двусторонним сверхсловом (как и сказано во введении) над конечным алфавитом называется отображение из множества целых чи­ сел в этот алфавит. (Далее в данной главе мы будем говорить просто сверхсло­ во.) Множество всех сверхслов над алфавитом будет обозначаться через. Сдвигом называется любое отображение, которое сопоставляет сверх­ слову () сверхслово ( + ), где произвольное целое число, называемое величиной сдвига. В большинстве случаев будут рассматриваться сверхслова в алфавитах {, }, {,, } и в алфавите пар символов Использование этого обозначения для пары символов позволяет нам записы­ вать последовательность пар символов как две последовательности, записан­ ные одна под другой.

Будем называть двусторонним словом слово, в котором задано начало отсчёта, то есть отображение из конечного отрезка целых чисел в алфавит.

Будем использовать обозначение * для конкатенации слов и, а также * и * для приписывания буквы к слову слева или справа.

Элементарным цилиндром, соответствующим символу на позиции, называется множество таких сверхслов, что на позиции стоит. Тонким цилиндром называется конечное пересечение элементарных цилиндров, то есть, множество сверхслов, имеющих заданные буквы на позициях из некото­ рого конечного списка. Носителем тонкого цилиндра называется множество позиций из этого списка. Содержанием тонкого цилиндра со связным носи­ телем будем называть слово, образованное заданными символами на последо­ вательных позициях. Цилиндрически определимым множеством называет­ ся любой элемент сигма-алгебры, порождённой тонкими цилиндрами. Будем рассматривать вероятностные сигма-аддитивные меры, заданные только на цилиндрически определимых множествах. Зададим сходимость на мерах сле­ дующим образом: тогда и только тогда, когда для каждого тонкого цилиндра верно () ().

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

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

Определение 3.1 закончено.

Определение 3.2. Вероятностная мера, определенная на сигма-алгебре ци­ линдрически определимых множеств сверхслов, называется инвариантной (относительно сдвигов), если она приписывает одно и то же значение мно­ жествам сверхслов, отличающимся лишь сдвигом.

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

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

Пусть заданы действительные числа, от 0 до 1. Напомним построение операторов Тоома.

Flip+ превращает каждый символ в независимо с вероятностью Flip превращает каждый символ в противоположный независимо с ве­ Ann выделяет в сверхслове все вхождения и вычеркивает каждое из них (независимо от прочих) с вероятностью.

Каждый из этих операторов для любого исходного сверхслова задает некоторое распределение вероятностей на выходных сверхсловах. Чтобы при­ менить их к произвольной мере, надо усреднить эти распределения по данной мере на.

Симметричный оператор Тоома сим задается как композиция Flip и Ann (в указанной последовательности), а асимметричный оператор асим — как композиция Flip+ и Ann.

На самом деле, мы пока еще не определили оператор Ann. Тонкость в том, что в последовательности, полученной вычеркиванием, можно разными способами задать “начало отсчета”, то есть, член с нулевым номером. Нужно сделать это так, чтобы полученный оператор сохранял свойство меры быть инвариантной. Поясним, в чем здесь трудность.

Пусть, скажем, для определения начала отсчета мы берем первый невы­ черкнутый символ с неотрицательным номером. В качестве примера рассмот­ рим следующую инвариантную меру: она сопоставляет вероятности по 1/ периодическому сверхслову (с периодом 4) и трем его сдвигам:

Ясно, что при правильном определении после стирания всех вхождений (считаем для простоты, что = 1 ) должна получится инвариантная мера, которая сопоставляет вероятность 1/2 обоим сверхсловам из чередующихся плюсов и минусов.

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

Поэтому после стирания сверхслово · · ·... будет иметь вероят­ ность 1/4, а сдвинутое сверхслово · · ·... — вероятность 3/4.

3.4. Определение оператора Ann.

Чтобы определить оператор Ann, мы представим его как композицию двух операторов: первый из них, Duel, заменяет каждое вхождение с вероятностью на пару новых символов, а второй, Clean, стирает все символы. Определение оператора Duel не представляет проблемы, поскольку можно сохранить исходное начало отсчета: полученный оператор коммутирует со сдвигом и поэтому сохраняет инвариантность. Трудности со­ средоточены в определении оператора стирания Clean.

Определение 3.3. Определим оператор Clean. Сделаем это сразу в общем случае — определим оператор стирания всех символов из множества в сверхсловах над. Мы предполагаем, что вероятность наличия на любой заданной позиции символа из не равна 1.

Вероятность по мере Clean непустого слова 0... над алфави­ том задается следующей формулой:

В этой формуле — произвольные символы из алфавита. Дру­ гими словами, вхождению заданного слова в любой данной позиции ме­ ра Clean приписывает вероятность, равную сумме вероятностей всех слов, которые можно получить из вставкой элементов в произволь­ ном количестве между буквами, поделённой на суммарную вероятность символов не из.

Вероятность по мере Clean пустого слова по определению равна 1.

Для мер, не являющихся вероятностными, можно говорить об опера­ Более того, это же определение можно применять и к функциям на словах. Желательно, чтобы слова, отличающиеся только добавлением и удалением нулевых символов, входили или не входили в область определения одновременно.

Определение 3.4. Обозначим для всякого слова в алфавите через Splice () множество всех слов, которые можно получить из вставкой между символами символов из в произвольном порядке и количестве.

Замечание 3.1. Можно определить оператор Clean и другим способом, дающим тот же результат на основании неформального описания опера­ тора как “вычёркивания нулей”. Сначала рассмотрим условную меру 1, полученную ограничением на сверхслова, в которых в начале координат символ не из. Для любого сверхслова с таким свойством корректно опре­ делено вычёркивание всех вхождений символов из со сдвигом к началу координат. Нетрудно убедиться, что образ 1 под действием отображе­ ния вычёркивания равен Clean. Коэффициент 1 () в формуле для Clean () есть как раз вероятность условия “в начале координат стоит символ не из ”.

Замечание 3.2. Оператор Clean линеен.

Лемма 3.2. Определение 3.3 для любой инвариантной меры задаёт ин­ вариантную вероятностную меру.

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

Для пустого слова это требование обеспечивается нормирующим множителем. Для непустых слов нам понадобится следующее определение.

1() С помощью обозначения 3.4 мы можем написать, что Таким образом, для проверки того, что мера слова равна сумме мер всех слов, полученных приписыванием слева к исходному слову любой буквы из, нам нужно установить следующее равенство:

Множество Splice ( * ) состоит в точности из всех слов вида * *, где * и Splice (). Поэтому нам достаточно доказать, что при любом фиксированном Splice () имеет место равенство Чем отличаются левая и правая части этого равенства? В левой части стоит -вероятность события “сверхслово содержит подслово, начиная с нулевой позиции”. В правой части стоит -вероятность пересечения того же события с событием “в какой-то позиции с отрицательным номером имеется символ из ”. Вероятности этих двух событий совпадают. В самом деле, мера инвариантна относительно сдвигов, вхождения слова из бесконечного конца нулевых символов и одного ненулевого символа на различных позициях об­ разуют счётный набор взаимоисключающих событий.

Аналогичное рассуждение применимо для приписывания букв справа.

Лемма 3.2 доказана.

Таким образом, мы определили оператор Clean. Операторы Duel, Flip и Flip+ не требуют такого уточнения, а оператор Ann определяется как Clean Duel.

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

Проекция в этом определении понимается в следующем смысле. Каждо­ му слову над декартовым квадратом данного алфавита (алфавита пар букв) соответствует пара слов одной длины над этим алфавитом. Например, слову соответствует пара слов (, ). Такое же соответствие имеется и между последовательностями над декартовым квадратом алфавита и па­ рами последовательностей над самим алфавитом. Благодаря этому каждой мере на последовательностях над декартовым квадратом соответствует ме­ ра на парах последовательностей над исходным алфавитом. Первой (второй) проекцией меры называется мера, по которой распределены первые (вто­ рые) компоненты пар случайно выбранной по этой мере последовательности.

Если исходная мера инвариантна, то и обе ее проекции инвариантны.

Теорема 3.2. Отношение на мерах удовлетворяет первому и третьему условиям на стр. 20, но не удовлетворяет четвертому.

Замечание 3.3. Если считать, что в операторе Тоома Flip происходит после Ann, то выполнение второго условия очевидно: Flip+ отличается от Flip заменой некоторых минусов (обратно) на плюсы. Иначе вопрос становится достаточно сложным из-за немонотонности Clean и, соот­ ветственно, Ann. Этот вопрос мы рассматривать в данной работе не будем.

Доказательство. Докажем сначала первое условие (транзитивность).

Пусть даны инвариантные вероятностные меры,, такие, что. Значит, существует полупрямое произведение мер,, согласован­ ное с порядком, а также полупрямое произведение мер,, согласованное с порядком. Нам нужно установить существование полупрямого произведе­ ния мер,, согласованного с порядком.

Это легко доказать для вероятностных мер на конечных множествах. А именно, пусть,, — распределения вероятностей на некотором конечном упорядоченном множестве. Тогда можно определить распределение веро­ ятностей на 3 обладающие следующими двумя свойствами:

1) проекция на первую и вторую координаты равна, 2) проекция на вторую и третью координаты равна.

Например, можно определить формулой Это распределение соответствует такому процессу порождения слова :

мы сначала выбираем случайно, используя вероятностную меру. Затем мы выбираем случайно по условному распределению на первой коорди­ нате при условии, что вторая координата равна уже выбранному. Наконец, мы независимо выбираем по условному распределению на второй коор­ динате при известной первой.

Из свойств следует, что с вероятностью 1 относительно будут вы­ полнены неравенства. Поэтому в качестве искомой меры можно взять проекцию на первую и третью координаты.

Для дальнейшего важно понимать, что мера не определяется одно­ значно условиями 1) и 2). Пусть например = {0, 1} и обе меры, суть равномерное распределение на множестве 2. Тогда построенная нами ме­ ра является равномерным распределением на 3. При этом существует и другая мера со свойствами 1) и 2), например, равномерное распределе­ ние на множестве всех троек из 3, у которых первая и третья координата совпадают.

Перейдем теперь к случаю мер на пространстве двусторонних последо­ вательностей. Мы знаем два доказательства транзитивности и оба они некон­ структивны в том смысле, что мера не строится явно по данным мерам Неконструктивность возникает из-за применения следующей леммы (пре­ дельная точка, существование которой утверждает лемма, может быть не единственна).

Лемма 3.3. Последовательность счётных последовательностей веществен­ ных чисел из заданного отрезка имеет предельную точку (с точки зрения поточечной сходимости).

Доказательство. Будем вычёркивать некоторые последовательности, а неко­ торые будем отбирать как участвующие в сходимости к предельной точке.

Вначале мы ничего не выбрали и не вычеркнули.

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

На -м шаге шаге мы смотрим на элементы с номером во всех невы­ черкнутых последовательностях. Это ограниченная последовательность, она имеет предельную точку. Вычеркнем из неё элементы так, чтобы предель­ ная точка стала пределом. Вычеркнем все последовательности, в которых лежали вычеркнутые элементы. Выберем в окончательный ответ первую из оставшихся невычеркнутыми и невыбранными последовательностей.

По построению на каждой позиции элементы выбранных последователь­ ностей имеют предел, что и требовалось.

Следствием данного факта является следующая лемма:

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

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

Покажем теперь, что это же утверждение можно применять и к мерам.

Лемма 3.5. Любая последовательность конечных мер на сверхсловах име­ ет предельную точку, являющуюся мерой.

Если исходные меры были вероятностными, таковой будет и предель­ ная точка.

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

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

Ясно, что предельная функция тоже будет определена на словах такого вида.

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

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

Первое доказательство. Аналогично случаю конечных множеств, мы докажем существование вероятностной меры на сверхсловах над алфави­ том, проекция которой на первую и вторую координаты равна, а проекция на вторую и третью координаты —. В частности, в любой позиции с вероятностью 1 относительно первый символ будет не меньше второго, а второй не меньшего третьего, поэтому проекция меры на первую и третью координаты будет искомой мерой.

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

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

Определим множество состоящим из всех двусторонних слов (, ) над алфавитом, в которых длина и длина равны ровно. Множество конечно. Сужение меры на (которое мы понимаем как множество двусторонних слов (, ) над алфавитом, в которых длина и длина равны ровно ) задает распределение вероятностей на, которое мы обозначим через. То же самое верно для сужения меры на.

Причем, обе меры согласованы с покомпонентым порядком и вторая проек­ ция меры совпадает с первой проекцией меры. Как уже объяснялось, отсюда следует, что можно построить распределение вероятностей на 3, у которого проекция на первую и вторую координаты равны, а проекция на вторую и третью координаты равны.

Теперь рассмотрим предельную точку таких мер. Она и будет требуемой мерой. Транзитивность доказана.

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

Второе доказательство.

Переформулируем определение порядка на мерах так, что транзитив­ ность станет очевидной.

Определение 3.6. Верхним цилиндром называется объединение всех тон­ ких цилиндров, больших либо равных данному в смысле определения 3.5.

Верхним множеством называется конечное объединение верхних цилиндров с общим носителем.

Лемма 3.6. тогда и только тогда, когда для любого верхнего мно­ Доказательство. Везде в доказательстве будем использовать на по­ следовательностях, цилиндрах (и словах, задающих цилиндры) для обозна­ чения частичного покомпонентного порядка, а на мерах — для обозначения введённого порядка, транзитивность которого мы и доказываем.

Отсюда следует Пусть теперь вероятность любого верхнего множества по мере не мень­ ше, чем по. Нам нужно построить полупрямое произведение мер,, согласованное с порядком.

Пусть 2+1, 2+1 — меры, являющиеся ограничением мер, на ци­ линдры длины 2 + 1 с серединой в нулевой позиции. Определим меру 2+ на парах слов длины 2+1 с серединой в нулевой позиции (эти слова задают тонкие цилиндры, у носителя которых середина находится в нулевой позиции и длина равна 2 + 1 ), обладающую следующими двумя свойствами:

1) по мере 2+1 могут иметь ненулевую вероятность только те пары слов длины 2 + 1, у которых первая компонента больше или равна второй;

2) Проекция меры 2+1 на первую координату равна 2+1, а на вторую координату — 2+1.

Существование такой меры 2+1 следует из теоремы 0.4 из второй гла­ вы (которая позволяет явно построить меру на словах в алфавите пар сим­ волов с помощью теоремы Форда-Фалкерсона о потоке и разрезе).

Рассмотрим любую предельную точку этой последовательности мер.

Функция определена на всех двусторонних словах над.

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

Лемма 3.6 доказана. Из неё сразу следует, что отношение транзитивно (первое условие).

Третье условие (на стр. 0.3) следует из определения. Действительно, мно­ жество последовательностей, у которых в данной позиции стоит плюс, есть верхнее множество (и даже верхний цилиндр). Поэтому, если мера больше меры, то -вероятность этого множества не меньше его -вероятности.