Сверхслова, меры на них и их полупрямые произведения тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

М.В. Ломоносова»

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

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

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

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

Автореферат

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

О 4 СЕН 2014

Москва — 2014

005552107

Работа выполнена на кафедре математической логики и теории алгоритмов Механико-математического факультета ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова». Научный руководитель: Верещагин Николай Константинович,

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

доктор физико-математических наук, профессор (ФГБУН Институт систем информатики им. А.П. Ершова СО РАН) Михаил Николаевич Вялый, кандидат физико-математических наук, доцент (ФГБУН Вычислительный центр им. А. А. Дородницына РАН)

Ведущая организация: ФГБУН Санкт-Петербургское отделе-

ние Математического института им.

В.А.Стеклова РАН

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

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова» (г. Москва, Ломоносовский проспект, д. 27, сектор А). .

Автореферат разослан «17» сентября 2014 года.

Ученый секретарь диссертационного

совета Д.501.001.84, созданного на базе

ФГБОУ ВПО «МГУ имени М.В. Ломоносова»

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

профессор Иванов Александр Олегович

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

Актуальность работы. Диссертация относится к теории сверхслов и мер на них. Сверхслова над конечным алфавитом рассматриваются в разных областях математики; в частности, с ними связаны комбинаторика слов, теория клеточных автоматов, теория алгоритмической случайности и монадические теории.

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

В диссертации даны ответы на вопросы, поставленные к.ф.-м.н. М.Н. Вялым, акад. РАН проф. А.Л. Семёновым, к.ф.-м.н. А. Шенём. проф. А.Л. То-омо.м.

Почти периодичность сверхслов

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

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

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

Легко проверить, что понятие почти периодичности является ослаблением понятия периодичности. В частности, регулятор почти периодичности периодической последовательности с периодом Т ограничен сверху функцией п >->■ Т + п-1.

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

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

Ан.А. Мучников и Л.Л. Семёновым2 показано, что если подавать конечно-

1 M.Lothaire. Algebraic Combinatorics on Words. Cambridge University Press, 2002

2 An. Muchnik, A. Semenov, and M. Ushakov. Almost periodic sequences. Theoretical Computer Science,

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

Эти результаты сделали естественным вопрос о том, как ири этом изменяется регулятор. Если рассмотреть проекцию, то есть конечно-автоматное преобразование с одним состоянием, то регулятор не может увеличиться. В работах Ю.Л.Притыкпна4 и А.Л.Семёнова и Ан.А.Мучника3 фактически получена в общем случае верхняя оценка регулятора конечно-автоматного образа через регулятор исходного сверхслова. Но эта оценка очень быстро растет, что оставляло открытым вопрос об улучшении верхней оценки.

Сравнение мер через полупрямые произведения

Говорят, что мера Л на пространстве X х У является полупрямым произведением /t и v, если ее проекции равны /х и v, то есть, для любого измеримого А С X выполнено

А(Л х У) = ц(А), а также, для любого измеримого В С У выполнено

А(Л" х В) = v{B).

Примером полупрямого произведения мер р, и является их прямое произведение.

Полупрямые произведения мер, согласованные с отношением порядка, являются одним из примеров применения полупрямых произведений, не являю-

304:1 33, 2003

3 Ю. Л. Прпгыкин. Конечно-автоматные преобразования строго почта периодических последовательностей. Математические заметки, 80(5):7з1-7э6, 2006

4 Ю.Л. Притыкин. Почти периодичность, конечно-автоматные преобразования и вопросы эффективности. Известия вузов. Математика, 1:74-87, 2010

5 An. Muchnik, A. Semenov, and M. Ushakov. Almost periodic sequences. Theoretical Computer Science, 304:1-33, 2003

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

Пример 1. Даны распределения вероятности ß,v на одном и том же конечном множестве X. Требуется найти их полупрямое произведение Л, для которого вероятность события "первая координата совпадает со второй"' максимальна. Эта задача возникает при доказательстве некоторого неравенства, ограничивающего разницу между шенноновской энтропией //. и v в терминах статистического расстояния между ц и v (см., например, учебник по колмого-ровской сложности 6).

Пример 2. Одним из двух известных методов получения не шенноновских информационных неравенств является «метод независимизации», примененный в работе А. Шеня, А.Е. Ромащенко и Л.Бьянвеню7 и работе К.С. Макарычева, Ю.С.Макарычева, А.Е. Ромащенко и Н.К. Верещагина Мы изложим этот метод вкратце, а для более подробного знакомства отсылаем читателя к книге по колмогоровской сложности 9. В простейшей ситуации метод состоит в следующем: пусть дано некоторое неравенство, в которое входит шенноновские энтропии случайных величин а., ß и 7, шенноновская энтропия пары случайных величин (a,ß) и шенноновская энтропия пары случайных величин (а, у) (например, 2 H (а) + 2 H{ß) + 2Я(т) < ЗЯ (а, /3) + ЗЯ(а, 7)). Допустим, удалось доказать это неравенство для любых трёх совместно распределённых случайных величин а,/3,7 таких, что случайные величины ß и 7 независимы при всяком известном исходе случайной величины а. Тогда это неравенство истинно и для

6 Н.К. Верещагин, В.А. Успенский, and А. Шенъ. Колмогоровская сложность и алгоритмтическая случайность. МЦНМО, М., 2012

7 L. Bienvenu, A. Romashchenko, and A. Shen. Sparse sets. In Procecdings of Symposium on Cellvlar Automala, Journées Automates Cellulaires (JAC 2008). pages 18- 28, 2008

8 K. Makarychev, Yu. Makarychev, A. Romashchenko, and N. Vereshchagin. A new class uf non shannon type inequalities for entropies. Communications in Information and Systems, 2(2):147--166, 2002

9 Н.К. Верещагин, В.А. Успенский, and A. Шень. Колмогоровская сложность и алгоритлтическая случайность. МЦНМО. М., 2012

любых вообще совместно распределённых случайных величин а, уЗ, 7.

В самом деле, пусть даны произвольные совместно распределённые случайные величины от, /3,7 с исходами в некоторых множествах X, У, Z, соотсвет-ственно. Обозначим через р, распределение случайной величины (а, /3) (с исходами в X х У), а через V — распределение пары случайной величины (0,7) (с исходами в X х .£). Несложно убедиться, что существует полупрямос произведение А раепредапеннй р и V (на множестве I х У х X х 2), относительно которого с вероятностью 1 первая и третья координаты совпадают, а вторая и четвёртая координаты независимы при любой известной первой (= третьей) координате. Обозначим через а',/З',а', 7' случайные величины, равные первой, второй, третьей и четвёртой координате четвёрки, выбранной случайно по распределению А. Тогда 7' и /3' независимы при всяком известном исходе случайной величины а', поэтому исходное неравенство выполнено для этой тройки случайных величин. С другой стороны, распределение пары (а', 7') такое же, как и у пары (а, 7). То же самое верно и для пары (а, /3) и для каждой из случайных величин а,/3,7. Поэтому шенноновская энтропия пары (а', У) та же, что и у пары (а, 7), и то же самое верно для пары [а, в) н для а, В, 7 по отдельности. Следовательно, исходное неравенство верно и для данной (произвольной) тройки «,/3,7.

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

Пример 3. Из этого примера и возник вопрос, изученный во второй главе. Пусть X = У есть пространство всех сверхслов из нулей и единиц. Пусть /х есть бернуллиевская мера на X с рациональным параметром р\, а V есть бернуллиевская мера на У с рациональным параметром р2 > рь (Бернуллиевская мера с параметром р определяется, как распределение вероятностей на последовательностях, полученных в результате бесконечного числа незави-

симых бросаний монетки, выдающей 1 с вероятностью р и 0 с вероятностью 1 — р.) Будем рассматривать бесконечные 0-1-последовательности, случайные по Мартин-Лёфу относительно распределения р. (определение случайности по Мартин-Лёфу можно найти, например, в учебнике по колмогровс.кой сложности10). В работе А. Шеня, А.Е. Ромащенко и Л.Бьянвеню 11 доказано, что в любой такой последовательности можно заменить некоторые нули на единицы так, чтобы полученная последовательность была случайна по Мартин-Лёфу по распределению v. Это доказывается с помощью рассмотрения вычислимого полупрямого произведения распределений ц и v, относительно которого с вероятностью 1 последовательность х покомпонентно меньше последовательности у (несложно доказать, что у бернуллиевских распределений с вычислимыми параметрами р2 > р\ такое полупрямое произведение в самом деле существует). Точнее, доказан следующий общий факт: если у вычислимых распределений ц и v на пространстве бесконечных 0-1-последовательностей существует вычислимое полупрямое произведение Л, относительно которого с вероятностью 1 последовательность х покомпонентно меньше последовательности у, то в любой бесконечной последовательности, случайной по Мартин-Лёфу относительно распределения ц можно заменить некоторые нули на единицы так, чтобы полученная последовательность была случайна по Мартин-Лёфу по распределению

V.

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

Отношение Тоома на мерах на сверхсловах

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

10 Н.К. Верещагин, В.А. Успенский, and А. Шень. Колмогороеская сложность и а.ггоритп.итичсская случайность. МЦНМО, М., 2012

11 L. Bienvenu, A. Romashcheiiko, and A. Shen. Sparse sets. In Proceedings of Symposium on Cellular Automata, Journées Automates Cellulaires (JAC 2008), pages 18-28, 2008

седей. Исторически клеточные автоматы восходят к физическим моделям на решётках (таким как модель Изинга намагничивания кристалла). С середины XX века их также рассматривают и в качестве вычислительных моделей.

Вопрос сохранения вероятностным клеточным автоматом разницы между двумя конфигурациями представляет интерес при разных подходах к изучению клеточных автоматов. Этот вопрос может быть интерпретирован и как хранение информации в вычислительной системе с помехами, и как моделирование фазового перехода, и как изучение условий эргодичности с точки зрения теории динамических систем. Для двумерных клеточных автоматов сохраняющий информацию при помехах клеточный автомат был построен А.Л. Тоомом12. П.Гач13 построил пример одномерного клеточного автомата, в котором все вероятности перехода положительны и который способен надёжно сохранять один бит информации несмотря на помехи.

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

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

12 А.Л. Тоом. Устойчивые п притягивающие траектории в мношкомпонентных системах. In Р. Л. Добрушин, editor, Многокомпонентные, системы. Наука, Москва, 1978

13 Р. Gäcs. Reliable cellular automata with self-organization. Journal of Statistical Physics, 103(l/2):45-267,

2001

14 A. Toom. N'on-ergodicity in a 1-d particle process with variable length. Journal of Stat. Physich, 115:895-924, 2004

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

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

15 A. Toom. Non-ergodicity in a 1-ii particle process with variable length. Journal of Stat. Physics, 115:895-924, 2001

вается равносильным сохранению преобладания минусов. Однако стандартное отношение сравнения на мерах на двусторонних сверхсловах не позволяет доказать монотонность рассматриваемых операторов из-за возможности стирания.

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

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

Для применения этого отношения требовалось доказать транзитивность этого отношения. Этот вопрос неоднократно формулировался А.Л. Тоомом в докладах, но долгое время оставался открытым.

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

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

1. Получена нижняя оценка для регулятора почти периодичности прямого

16 Л. Тоом. Клеточные автоматы. НМУ, спецкурс, 2004

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

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

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

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

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

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

• «Колмогоровский семинар по сложности вычислений и сложности определений» под руководством проф. Н.К. Верещагина, к.ф.-м.н. А.Е. Рома-щенко, акад. А.Л. Семёнова, к.ф.-м.н. А.Шеня (неоднократно с 2006 по 2011 год)

• на 8-й международной конференции по вычислимости, сложности и случайности (СС11-2013), 23-27 сентября, Москва

• на семинаре «Вычислимость и неклассические логики» под руководством доц. В.Н. Крупского, доц. Е.Ю.Ногиной, доц. В.Е.Плиско (2010 год)

• на семинаре по дискретной математике ПОМИ РАН под руководством к.ф.-м.н. Д.М. Ицыксона, д.ф.-м.н. Э.А. Гнрша, (2011 год)

• на семинаре WIWAD-2007 (мероприятие-спутник международного симпозиума по компьютерным наукам в России (CSR-2007), 7 сентября 2007 года, Екатеринбург).

Кроме того, на семинаре "Space-Time Phases" (мероприятие-спутник ECCS12, 6 сентября 2012 года, Брюссель) A.JI. Тоом представлял совместную работу с автором.

Публикации. Материалы диссертации опубликованы в 3 печатных работах, из них 3 статьи в рецензируемых журналах [1-3], из них 3 работы — в журналах, включенных Высшей аттестационной комиссией Минобрнауки России в список изданий, рекомендуемых для опубликования основных научных результатов диссертаций на соискание ученой степени кандидата и доктора наук-

Структура диссертации. Диссертация состоит из введения, трёх глав и списка цитируемой литературы. В списке цитируемой литературы 18 наиме-ноаний. Работа изложена на 98 страницах, содержит 3 рисунка.

Содержание работы

0.1. Регуляторы почти периодических последовательностей

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

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

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

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

Основные определения

Определение 0.1. Пусть дан некоторый алфавит Е. Словом над этим алфавитом называется конечная последовательность букв (элементов алфавита). Сверхсловом называется бесконечная последовательность букв. Мы считаем, что буквы в сверхслове занумерованы элементами Н; в последующих главах мы будем называть двусторонними сверхсловами бесконечные двусторонние последовательности букв, то есть отображения из Ъ в

Свсрхслово <21, от, ■ • •, ап,... называется периодическим, если для некоторого целого положительного числа Т при всех п выполняется равенство ап — ап+т-Как обычно, наименьшее такое число Т называется периодом.

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

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

Конечный преобразователь с входным алфавитом £ и выходным алфавитом Д задаётся множеством внутренних состояний <2, начальным состоянием до С <3 и функцией перехода ^ : Ц х Е -> (3 х Д. Конечный преобразователь получает на вход символы из алфавита Е по одному; функция перехода

по состоянию на каждом шаге и входному символу возвращает состояние на следующем шаге и зыходной символ. Таким образом, подавая на вход некоторое сверхслово А = aoai... мы получаем последовательность состояний qoQi ■ ■ ■ н выходных символов babi... такие, что F(qn.an) - (qn+\,bn); выходное слово при этом будет В — —

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

История рассматриваемых понятий

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

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

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

Например, сверхслово Olli... является заключительно периодическим, но не почти периодическим. А сверхслово 00000110100110010110... (полученное добавлением четырех нулей к последовательности Туэ-Морса) является заключительно почти периодическим, но не является заключительно периодическим.

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

Ан.А. Мучник и А.Л. Семёнов18 доказали, что если подавать конечному автомату на вход обобщенно почти периодическое сверхслово, то на выход он будет выдавать обобщенно почти периодическое сверхслово. В работе Ю.Л. При-тыкина 19 доказан аналог этого результата для более узкого класса: показано, что заключительно почти периодические сверхслова под действием конечного автомата переходят в заключительно почти периодические.

Эти результаты сделали естественным вопрос о том, как при этом изменяется регулятор. Если рассмотреть проекцию, то есть конечно-автоматное преобразование с одним состоянием, то регулятор не может увеличиться. В работе Ю.Л. Притыкина20 и работе Ан.А. Мучника и А.Л. Семёнова21 фактически получена в общем случае верхняя оценка регулятора конечно-автоматного образа через регулятор исходного сверхслова. Но эта оценка очень быстро растет.

Будем обозначать через функцию, являющуюся n-кратной компози-

цией функции /(•) с собой: fon(k) = /(/(... f [к)...)).

7i раз

Теорема 0.1 (работе Ю.Л. Притыкина22 и работе Ан.А. Мучника и А.Л. Семёнова23). Если у заключитп&гъио почти периодического сверхслова регулятор

17 Ю. Л. Притыкин. Конечно-автоматные преобразования строго почти периодических последовательностей. Математические заметки, 80(5):751-756, 2006

18 An. Muchnik, A. Semenov, and М. Ushakov. Almost periodic sequences. Theoretical Computer Science, 304:1-33, 2003

19 Ю. Л. Притыкин. Конечно-автоматные преобразования строго почти периодических последовательностей. Математические, заметки, 80(5):751-756, 2006

20 Ю.Л. Притыкин. Почти периодичность, конечно-автоматные преобразования и вопросы эффективности. Известия вузов. Математика, 1:74-87, 2010

21 An. Muchnik, A. Semenov, and М. Ushakov. Almost periodic sequences. Theoretical Computer Science, 304:1-33. 2003

22 Ю.Л. Притыкин. Почти периодичность, конечно-автоматные преобразования и вопросы 'эффективности. Известия вузов. Математика, 1:74-87, 2010

23 An. Muchnik. A. Semenov, and М. Ushakov. Almost periodic sequences. Theoretical Computer Science.

не превосходит G(l) — 1 и автомат имеет п состояний, т.о у его образа под действием автомата регулятор (в смысле определения 0.3) не превосходит Gcn(l).

Определение 0.4. Прямым произведением двух сверхслов а = aian... и Ь = b\bi... называется сверхслово а ® 6, состоящее из пар соответствующих символов в сверхсловах а и Ь, то есть сверхслово (ai, fri)(a2, M • • • Аналогично определяется прямое произведение конечных слов одной длины. Алфавитом прямого произведения сверхслов является декартово произведение исходных алфавитов.

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

На докладе Ю.Л. Притыкина21. в котором были доказаны основные результаты двух его работ2026, М.Н. Вялый поставил вопрос о возможности уменьшения верхней оценки. После того, как ответ на этот вопрос был дан автором диссертации, АЛ. Семёнов поставил вопрос о том, для какого класса конечных автоматов можно провести аналогичное рассуждение.

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

304:1-33, 2003

24 Ю.Л. Притыкин. Действие конечных автоматов на почта периодические последовательности, доклад на Колмогоровском семинаре, 2005

25 Ю. Л. Притыкин. Конечно-автоматные преобразования строго почти периодических последовательностей. Мате-иатические заметки, S0(5):751-?Í)G, 2006

26 Ю.Л. Притыкин. Почти периодичность, конечно-автоматные преобразования и вопросы эффективности. Известия вузов. Математика, 1:74-87, 2010

Основной результат главы

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

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

Теорема 0.2. (опубликовано в [1]) Если задана возрастающая функция натурального аргумента F, то существует почти периодическое сверхслово А нулей и единиц со следующими свойством. Для всехп > 100 и бесконечно .многих I значение на I регулятора почти периодичности сверхслова А ® Cycle,, превышает (max{F,/} 4- 1)°LsbJ (i), где Cyclen обозначает сверхслово (k mod п), a f — регулятор почти периодичности сверхслова А.

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

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

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

1) Для бесконечного количества аргументов fB превышает F. Более того, эти аргументы выстроены в цепочку: существует, последоватыьностъ натуральных чисел Li, такая что

F(Ь{) < < fB(Li) < Li+1.

2) Для любого n > 2 и любого i регулятор почти периодичности В ® Сус1е„ удовлетворяет, неравенствам /взСус1е„(£г) > £¿+«-2 ,)•

S) Для любого достаточно большого п регулятор почти периодичности всё того же прямого произведения В ® Сус1еп на всех достаточно болыиих значениях аргументов превышает /д'_3.

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

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

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

Основные определения

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

27 Л. Шень. Редкие множества, доклад на Колмогоровском семинаре, 2009

множеств А С X п В С У выполнено равенство

{ц х !/)(Д х В) — ц(А) х и{В).

Говорят, что мера Л на пространстве X х У является полупрямым произведением ц и V, если ее проекции равны ц и и, то есть, для любого измеримого А С X выполнено

А (А х У) = р(А), а также, для любого измеримого В С У выполнено

\(Х х В) = 1у(В).

Примером полу прямого произведения мер /I, V является их прямое произведение.

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

В терминах случайных величин ц находится в отношении Меи (обозначается цМу), если существуют две случайные величины £ и Г) на одном вероятностном пространстве со значениями в X, У, распределения которых равны д и I/, соответственно, и для которых £ находится в отношении М с г] (во всех точках вероятностного пространства).

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

Рассмотрим множество £ = {0,1}. Через X/' обозначим пространство сверхслов из нулей и единиц. Введем на нем покомпонентный частичный порядок: Х0Х1Х2... ^ УоУ\У2 •••! если .Т; ^ у; при всех i. Будем рассматривать

меры, заданные на снгма-алгебре, порожденной множествами сверхслов, являющихся продолжениями заданных конечных слов. Мера р на пространстве £N называется вычислимой, если существует алгоритм, который по е € Q, s > 0, и конечному слову х в алфавите Е находит с точностью £ меру множества всех бесконечных продолжений х (см., например, учебник но колмогоровской сложности28). Аналогично определяются меры и их вычислимость на пространстве £n X измеримыми являются элементы сигма-алгебры, порожденной множествами пар сверхслов, первое из которых является продолжением одного слова, а второе - - другого слова. Алгоритм должен по s > 0 и словам х, у находить с точностью £ меру множества всех пар, в которых первая компонента продолжает слово х, а вторая — слово у.

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

Существование полупрямых произведений, согласованных с отношениями

Из теоремы Форда-Фалкерсона. 2а о максимальном потоке и разрезе следует следующий простои критерий того, что распределение р находится в отношении M с v. приведённый, например, в работе 30:

Теорема 0.4. [Автор неизвестен/ Распределение ¡i находится в отношении M с и, тогда и только тогда, когда не существует, подмножеств А с X.

28 Н.К. Верещагин, В.А. Успенский, and А. Шень. Колмогоровская сложность и а.г?ориггштическая случайность. МЦНМО, М., 2012

29 Т. Кормен, Ч. Лейзерсон, and Р. Ривест. Алгоритмы: построение и анализ. МЦНМО, M., 2001

30 L. Bienvenu, A. Romashchenko, and A. Shen. Sparse sets. In Proceedings of Symposium on Cellular Automata, Journées Automates Cellulaires (JAC ZOOS), pages 18-28. 2008

В <zY, таких что все M-соседи А лежат в В и ц(А) > v{B).

Если же X = У и M — отношение порядка (транзитивное рефлексивное отношение), то критерий можно переформулировать так: ß(A) < v{A) для всякого замкнутого вверх множества А С X. (В самом деле, можно считать, что В состоит только из соседей, тогда оно замкнуто вверх в силу транзитивности отношения порядка и содержит А в силу рефлексивности, а значит можно замкнуть А вверх.)

Повторим наиболее существенный для диссертации пример примерения полупрямых произведений вероятностных мер. Из этого примера и возник вопрос, изученный во второй главе. Пусть X = У есть пространство всех сверхслов из нулей и единиц. Пусть р есть бернуллиевская мера на X с рациональным параметром pi, а V есть бернуллиевская мера на У с рациональным параметром Р2 > Pi- (Бернуллиевская мера с параметром р определяется, как распределение вероятностей на последовательностях, полученных в результате бесконечного числа независимых бросаний монетки, выдающей 1 с вероятностью р и 0 с вероятностью 1—р.) Будем рассматривать бесконечные 0-1-последовательности, случайные по Мартин-Лёфу относительно распределения /г (определение случайности по Мартин-Лёфу можно найти, например, в 31 ). В работе 32 доказано, что в любой такой последовательности можно заменить некоторые нули на единицы так, чтобы полученная последовательность была случайна по Мартин-Лёфу по распределению v. Это доказывается с помощью рассмотрения вычислимого полупрямого произведения распределений ¡i и г/, относительно которого с вероятностью 1 последовательность х покомпонентно меньше последовательности у (несложно доказать, что у бернуллиевских распределений с вычислимыми параметрами р2 > pi такое полупрямое произведение в самом деле существует).

31 Н.К. Верещагин, В.А. Успенскпй, and А. Шень. Колмогоровская сложность и алгоритмтинеская случайность. МЦНМО, М., 2012

32 L. Bienvenu, A. Romaslichenko, and A. Shen. Sparse sets. In Proceedings of Symposium on Cellular Automata, Journées Automates Cellulaires (JAC ZOOS), pages 18-28, 2008

Точнее, доказан следующий общий факт: если у вычислимых распределений р и и на пространстве бесконечных 0-1-поеледователыюстей существует вычислимое полупрямое произведение А, относительно которого с вероятностью 1 последовательность х покомпонентно меньше последовательности у, то в любой бесконечной последовательности, случайной по Мартин-Лёфу относительно распределения ц можно заменить некоторые нули на единицы так, чтобы полученная последовательность была случайна по Мартин-Лёфу по распределению и.

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

Основной результат главы

Теорема 0.5. (опубликовано в /2/) Существуют две вычислимые меры р и и на Еы, которые имеют полупрямое произведение, согласованное с отношением по не имеют вычиааимого полупрялюго произведения, согласованного с отногиениель

0.3. Транзитивность отношения Тоома на мерах на сверхсловах

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

Данное отношение было введено с целью изучения вероятностных одно-

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

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

Как мы уже упоминали, А.Л. Тоом построил оператор, в котором почти все вероятности перехода положительны и который сохраняет один бит информации.

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

33 A. Toom. Non-ergodicity in a 1-d particle process with variable length. Journal of Stat. Physics, 115:895-924,2004

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

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

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

Нетрудно понять, что достаточно существования отношения со следующими свойствами:

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

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

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

34 А. Тоом. Клеточные автоматы. НМУ, спецкурс, 2004 , ' .

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

монотонности:

д > V =>■ А(ц) ^ А(1>).

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

^ГсимС^о) = ^астЛГ^СРо)) > (неравенство между операторами) Тст,(Т^и1({1о)) ^ (монотонность и предположение индукции) Тст<{Т^(/г0)) =

По первому свойству такую цепочку неравенств можно заменить на одно неравенство, откуда следует Г^ям(/(0) )? Т^{цо). Требуемое утверждение после этого следует из теоремы для ассимметричного оператора и третьего свойства (отношение между мерами гарантируег отношение между рассматриваемыми вероятностями).

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

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

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

доказана монотонность оператора Duel относительно рассматриваемого отношения.

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

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

Автор выражает глубокую признательность " У

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

Автор благодарен академику РАН A.JI. Семёнову,

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

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

Список публикаций автора по теме диссертации

1. М. А. Раскин. О нижней оценке регулятора прямого произведения почти периодической и периодической последовательностей. Вестник Московского Университета. Серия 1. Математика и механика., (6):7—11, 2011

2. М. А. Раскин. Согласованная с отношением порядка копроекция вычислимых мер не всегда вычислима. Вестник Московского Университета. Серия 1. Математика и механика., (2): 17—19, 2012

3. М. А. Раскин. Частичный порядок Тоома транзитивен. Проблемы передачи информации, 48(2):79-99, 2012

Отпечатано в копицентре « СТ ПРИНТ » Москва, Ленинские горы, МГУ, 1 Гуманитарный корпус, e-mail: globus9393338@yandex.ru тел.: 8 (495) 939-33-38 Тираж 100 экз. Подписано в печать 25.06.2014 г.