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

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

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

Для этого заме­тим, что если ∈ , то по лемме вероятность события 2 = , 2 = равна0 (поскольку ̸= и ̸= ), а если ∈ , то опять же по лемме эта веро­ятность равна 1/2. Руководствуясь этим, на входе отделитель с точностью1/4 вычисляет вероятность события 2 = , 2 = . и выдаёт 0, если прибли­жённое значение меньше 1/4, и 1, иначе. Таким образом, из существованиявычислимого полупрямого произведения следует существование отделителя и , что противоречит предположению об их неотделимости.Осталось перейти от построенного нами шестиэлементного множества к последовательностям нулей и единиц. Это легко сделать, вложив в49пятимерный булев куб с покоординатными сравнениями, например, так: = 00010, = 00100, = 01110, = 10110, = 10001, = 01001(вместо каждой буквы мы пишем пять битов).

Можно также обойтись и бу­левым квадратом: = 00, = = = 01, = 11, = 10Это вложение не даёт в точности того порядка, как на Рис. 2.2. Но можнозаметить, что в доказательстве были использовано только то, что ̸= , ̸= , каждое из , меньше или равно каждого из , и несравнимость , .Указанное вложение эти свойства сохраняет. Теорема доказана.50Глава 3Меры на сверхсловах и клеточные автоматы3.1.

Постановка задачиВ своих работах А.Л. Тоом рассматривал следующие операторы на ме­рах.Пусть заданы действительные числа , от 0 до 1. Рассмотрим следу­ющие три оператора на инвариантных мерах (через них мы и определимоператоры Тоома).∙ Flip+ превращает каждый символ ⊖ в ⊕ независимо с вероятностью;∙ Flip превращает каждый символ в противоположный независимо с ве­роятностью ;∙ Ann выделяет в сверхслове все вхождения ⊕⊖ и вычеркивает каждоеиз них (независимо от прочих) с вероятностью .Каждый из этих операторов для любого исходного сверхслова задаетнекоторое распределение вероятностей на выходных сверхсловах. Чтобы при­менить их к произвольной мере, надо усреднить эти распределения по данноймере на .Симметричный оператор Тоома сим задается как композиция Flip иAnn (в указанной последовательности), а асимметричный оператор асим —как композиция Flip+ и Ann .На самом деле, это описание не определяет оператор Ann .

Более точноеопределение будет дано ниже.В работе [13] сформулировано следующее предположение.Гипотеза 1 (А.Л. Тоом) Пусть исходное состояние (состояние в ну­левой момент) процесса, порождённого симметричным оператором Тоома51состоит из одних минусов. Тогда для любых положительных , найдется(достаточно малое) положительное , для которого выполнено следующее.Для каждого момента времени вероятность того, что в этот моментданная компонента находится в состоянии ⊕ , меньше .Очевидно, что эта гипотеза эквивалентна симметричной гипотезе, полу­чающейся из нее заменой ⊕ ↔ ⊖ .Теорема 3.1 ([13]).

Гипотеза 1 верна для асимметричного оператора Тоо­ма. Точнее, для всех , и всех моментов времени вероятность плюса вданной клетке не превосходит 300/2 .Напомним свойства 0.3 отношения сравнения мер < , нужные нам длядоказательства гипотезы.1. Отношение < транзитивно.2. асим < сим , где сим , асим обозначают, соответственно симметричныйи асимметричный операторы Тоома.3. Если < , то -вероятность плюса в данной клетке больше или равна -вероятности плюса в данной клетке.4. Хотя бы один из двух операторов Тоома обладает следующим свойствоммонотонности: < ⇒ () < ().Точнее, нам нужно чтобы для любого положительного существова­ло положительное , для которого выполнено второе и четвертое свойство(напомним, что операторы Тоома задаются параметрами , ).Лемма 3.1. Если существует отношение < на инвариантных мерах, удо­влетворяющее перечисленным свойствам, то из утверждения теоремы 3.1следует гипотеза 1.52Доказательство.

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

Сдругой стороны по второму свойству сим ( ) < асим ( ) = +1 . По транзи­тивности (первое условие) получаем +1 < +1 .Из доказанного и третьего свойства следует, что для любого моментавремени -вероятность плюса не меньше -вероятности плюса. Поэтомуиз теоремы 3.1 следует гипотеза 1. Лемма доказана.В качестве кандидата на подходящее отношение < А.Л. Тоом выдвинулдва отношения, которые мы обозначим > и D (определения будут даныниже). Первое из них удовлетворяет первому и третьему свойствам, но, какмы показываем в настоящей работе, не удовлетворяет четвертому свойству.Непосредственно из определения следует, что второе отношение D удо­влетворяет второму и третьему условиям.

А вот транзитивность была сфор­мулирована в качестве гипотезы и оставалась недоказанной. Доказательствоэтого факта и составляет основной результат настоящей главы. Выполненоли четвертое свойство, в настоящий момент неизвестно. Если удастся его до­казать, то гипотеза Тоома будет доказана.3.2. Используемые базовые понятия и обозначенияОпределение 3.1. Двусторонним сверхсловом (как и сказано во введении)над конечным алфавитом называется отображение из множества целых чи­сел в этот алфавит. (Далее в данной главе мы будем говорить просто сверхсло­во.) Множество всех сверхслов над алфавитом Σ будет обозначаться через53Σ∞ . Сдвигом называется любое отображение, которое сопоставляет сверх­слову ↦→ () сверхслово ↦→ ( + ) , где произвольное целое число,называемое величиной сдвига. В большинстве случаев будут рассматриватьсясверхслова в алфавитах {⊕, ⊖} , {⊕, ⊙, ⊖} и в алфавите пар символов{︂}︂⊕ ⊕ ⊕ ⊙ ⊙ ⊙ ⊖ ⊖ ⊖, , , , , , , ,.(3.1)⊕ ⊙ ⊖ ⊕ ⊙ ⊖ ⊕ ⊙ ⊖Использование этого обозначения для пары символов позволяет нам записы­вать последовательность пар символов как две последовательности, записан­ные одна под другой.Будем называть двусторонним словом слово, в котором задано началоотсчёта, то есть отображение из конечного отрезка целых чисел в алфавит.Будем использовать обозначение * для конкатенации слов и , атакже * и * для приписывания буквы к слову слева или справа.Элементарным цилиндром, соответствующим символу на позиции ,называется множество таких сверхслов, что на позиции стоит .

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

Будемрассматривать вероятностные сигма-аддитивные меры, заданные только нацилиндрически определимых множествах. Зададим сходимость на мерах сле­дующим образом: → тогда и только тогда, когда для каждого тонкогоцилиндра верно () → () .При обсуждении порядка всегда предполагается, что ⊕ > ⊙ > ⊖ .

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

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

Чтобы задать инвариантную меру, доста­точно сопоставить каждой конечной последовательности символов 1 . . . (то есть, слову) меру тонкого цилиндра{ : Z → Σ | (0) = 1 , . . . , ( − 1) = }.В дальнейшем мы будем называть эту величину “мерой слова 1 . . . ” иобозначать через () . Произвольная функция ↦→ () , отображающаяслова над алфавитом Σ в неотрицательные действительные числа, задаётинвариантную вероятностную меру тогда и только тогда, когда её значениена пустом слове равно 1 и для всех слов выполнены два равенства:() =∑︁∈Σ( * ),() =∑︁∈Σ( * ).55Пусть заданы действительные числа , от 0 до 1. Напомним построениеоператоров Тоома.∙ Flip+ превращает каждый символ ⊖ в ⊕ независимо с вероятностью;∙ Flip превращает каждый символ в противоположный независимо с ве­роятностью ;∙ Ann выделяет в сверхслове все вхождения ⊕⊖ и вычеркивает каждоеиз них (независимо от прочих) с вероятностью .Каждый из этих операторов для любого исходного сверхслова задаетнекоторое распределение вероятностей на выходных сверхсловах.

Чтобы при­менить их к произвольной мере, надо усреднить эти распределения по данноймере на .Симметричный оператор Тоома сим задается как композиция Flip иAnn (в указанной последовательности), а асимметричный оператор асим —как композиция Flip+ и Ann .На самом деле, мы пока еще не определили оператор Ann . Тонкость втом, что в последовательности, полученной вычеркиванием, можно разнымиспособами задать “начало отсчета”, то есть, член с нулевым номером.

Нужносделать это так, чтобы полученный оператор сохранял свойство меры бытьинвариантной. Поясним, в чем здесь трудность.Пусть, скажем, для определения начала отсчета мы берем первый невы­черкнутый символ с неотрицательным номером. В качестве примера рассмот­рим следующую инвариантную меру: она сопоставляет вероятности по 1/4периодическому сверхслову (с периодом 4)··· ⊕ ⊕ ⊖ ⊖ ⊕ ⊕ ⊖ ⊖ ⊕ ⊕ ⊖ ⊖...56и трем его сдвигам:··· ⊕ ⊖ ⊖ ⊕ ⊕ ⊖ ⊖ ⊕ ⊕ ⊖ ⊖ ⊕...··· ⊖ ⊖ ⊕ ⊕ ⊖ ⊖ ⊕ ⊕ ⊖ ⊖ ⊕ ⊕...··· ⊖ ⊕ ⊕ ⊖ ⊖ ⊕ ⊕ ⊖ ⊖ ⊕ ⊕ ⊖...Ясно, что при правильном определении после стирания всех вхождений ⊕⊖(считаем для простоты, что = 1 ) должна получится инвариантная мера,которая сопоставляет вероятность 1/2 обоим сверхсловам из чередующихсяплюсов и минусов.Однако при нашем определении получается вообще не инвариантная ме­ра.

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

. будет иметь вероят­ность 1/4, а сдвинутое сверхслово · · · ⊖ ⊕ ⊖ ⊕ ⊖ ⊕ . . . — вероятность 3/4.3.4. Определение оператора Ann .Чтобы определить оператор Ann , мы представим его как композициюдвух операторов: первый из них, Duel , заменяет каждое вхождение ⊕⊖с вероятностью на пару новых символов ⊙⊙ , а второй, Clean , стираетвсе символы ⊙ . Определение оператора Duel не представляет проблемы,поскольку можно сохранить исходное начало отсчета: полученный оператор57коммутирует со сдвигом и поэтому сохраняет инвариантность. Трудности со­средоточены в определении оператора стирания Clean .Определение 3.3.

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

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