Сверхслова, меры на них и их полупрямые произведения (1104768), страница 4

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

Текст из файла (страница 4)

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

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

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

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

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

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

Но эта оценка оченьбыстро растет.Напомним формулировку теоремы 0.1.24Будем обозначать через ∘ (·) функцию, являющуюся -кратной компо­зицией функции (·) с собой: ∘ () = ( (. . . ( ) . . . )).⏟⏞ разТеорема. (0.1) [[3, 4]] Если у заключительно почти периодического сверх­слова регулятор не превосходит () − 1 и автомат имеет состояний,то у его образа под действием автомата регулятор не превосходит ∘ ().Эта же оценка имеет место для регулятора прямого произведения за­ключительно почти периодического сверхслова и периодического сверхсловас периодом .1.3. Основной результат о почти периодическихсверхсловахАккуратная формулировка утверждения относительно точности верх­ней оценки регулятора образа чуть сложнее, чем хотелось бы.

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

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

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

Для всех > 100 и бесконечно многих значениена регулятора обобщённой почти периодичности сверхслова ⊗Cycle пре­вышает (max{, }+1)∘⌊ 30 ⌋ (), где Cycle обозначает сверхслово ( mod ),а — регулятор почти периодичности сверхслова .Эта теорема показывает, что в теореме 0.1 количество итераций функции должно расти линейно с ростом .1.4. Конструкция требуемого сверхсловаМы определим сверхслово вместе с числовой последовательностью , так что1) +1 > ( );2) для регулятора сверхслова выполнено неравенство +1 > ( );263) для > > 100 значение на регулятора почти периодичностисверхслова ⊗ Cycle превышает +⌊ ⌋ .30Сначала убедимся, что этого будет достаточно для доказательства теоре­мы.

Из первого и второго свойств следует, что + > (max{, }+1)∘ ( ).⌊︀ ⌋︀Подставив в это неравенство = 30и применив третье свойство последова­тельности и сверхслова , мы получим утверждение теоремы для = и произвольного > .Рассмотрим следующие слова из нулей единиц:0 = 100000010,0 = 1000000110,0 = 10000001110,+1 = ( )10+1 −10 ,+1 = ( )10+1 −10 ,+1 = ( )10+1 −10 .В этих формулах 1 , 2 , .

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

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

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

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

Характеристики

Список файлов диссертации