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

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

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

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

Таким образоммы сможем приближать (Γ ) снизу и наши приближения будут сходиться к42(Γ ). Правда, мы не знаем, в какой момент у нас уже имеется приближениес точностью . Для этого надо вычислять приближения снизу также и длявсех остальных слов ′ той же длины, что и . Когда сумма всех этих прибли­жений снизу станет больше 1 − , мы будем уверены, что точность каждогоиз них не хуже . Аналогичное верно и для вероятностных мер на ΣN × ΣN .2.2. Основной результат.В этом разделе мы предъявим две вычислимые вероятностные меры напространстве бесконечных 0-1-последовательностей, которые имеют полупря­мое произведение, согласованное с отношением покомпонентного порядка, новсе такие полупрямые произведения невычислимы.Напомним формулировку теоремы 0.5.Теорема.

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

Оно будет содержать шесть элементов, называемых, , , , , с частичным порядком: < , < , < , < (см. Рис. 2.2).cdabefРис. 2.2. Отношение частичного порядка43Сначала рассмотрим следующие два распределения на последовательно­стях из букв , , , . Пусть 0 , 1 , 2 , . . . независимы и принимают значения и с вероятностью 1/2. Аналогичным образом пусть 0 , 1 , 2 , .

. . независи­мы и принимают значения и с вероятностью 1/2. У случайных величин = 0 1 2 . . . и = 0 1 2 . . . есть много различных полупрямых произведе­ний. Можно считать, например, что = при = и = при = ;можно поменять и местами; наконец, можно считать и независимыми.Эти три варианта соответствуют трем матрицам совместного распределениядля и :⎛⎝1/2001/2⎠⎞0 1/2⎠⎝1/2 0⎛⎛⎞,,⎝1/4 1/41/4 1/4⎞⎠.(2.1)Проекции у этих распределений (суммы по строкам и столбцам) одинаковы,хотя сами распределения разные.Распределения на и будут играть в наших рассуждениях вспомога­тельную роль. А именно, для распределений и , которые мы построим, такбудут распределены буквы на чётных позициях.

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

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

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

. перечисляет безповторений множество .Нечётные члены последовательности определяется через её четныечлены следующим детерминированным правилом:⎧⎪⎨, если 2 = ,2+1 =⎪⎩, если 2 = .Напомним, что 2 выбирается случайно среди букв , с равномернымраспределением. Таким образом, первое распределение полностью задано.Нетрудно убедиться, что оно вычислимо. В самом деле, чтобы вычислить ме­ру множества всех продолжений слова нужно сделать следующее: если вслове есть буквы, отличные от , , , , то мера равна нулю. Иначе, длякаждой нечётной позиции 2 + 1 в вычислим .

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

Для чётных :2+1 =⎧⎪⎨,если 2 = ,⎪⎩, если 2 = ,а для нечётных — всё наоборот:⎧⎪⎨, если 2 = ,2+1 =⎪⎩, если 2 = .Распределение вероятностей теперь тоже полностью определено. Его вы­числимость доказывается так же, как и вычислимость распределения .Осталось понять, почему у распределений , есть полупрямое распре­деление, согласованное с покомпонентным частичным порядком, но нет та­кого вычислимого полупрямого произведения. Сначала докажем существова­ние. В качестве полупрямого произведения распределений , можно взятьраспределение, порождаемое следующим процессом:Для всех натуральных чисел (независимо друг от друга):если = ∈ , то выбираем с равными вероятностями 1/2 одиниз следующих двух случаев:(а) 2+1 = 2+1 = , 2 = , 2 = ,(б) 2+1 = 2+1 = , 2 = , 2 = ,если = ∈ , то выбираем с равными вероятностями 1/2 одиниз следующих двух случаев:(в) 2+1 = 2+1 = , 2 = , 2 = ,(г) 2+1 = 2+1 = , 2 = , 2 = ,46наконец, если не лежит ни в , ни в , то порождаем только па­ру букв 2 , 2 в соответствии с первой или второй из матриц (2.1)(можно использовать и любую их выпуклую комбинацию, напри­мер, третью матрицу).В результате этого процесса мы определим не только все буквы с чётныминомерами в , , но и все буквы с нечётными номерами.

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

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

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

По замечанию передформулировкой теоремы из существования порождающего распределение алгоритма следует существование и вычисляющего алгоритма.Можно вычислять меру , задаваемую данным отделителем, и непосред­ственно. Пусть нам, скажем, надо найти вероятность того, что по мере последовательность продолжает данное слово , а последовательность продолжает данное слово . Тогда мы для всех чётных позиций 2, которыеесть в или , применяем отделитель к . Затем мы смотрим, нет ли средипозиций, имеющихся в или , такой позиции 2 + 1, для которой = .Если буквы в и в позициях 2, 2 + 1 не согласованы с выходом отдели­теля (согласованность означает случаи (a) или (б), если отделитель выдал 0,и случаи (в) или (г), если он выдал 1; отсутствие указанной позиции 2 + 1в словах или не мешает согласованности), то вероятность равна нулю.Иначе она равна 2− , где обозначает количество свободных позиций в , — так мы называем все чётные позиции, которые присутствуют хотя бы водном из слов, и все нечётные позиции 2 + 1, для которых позиция 2 невходит ни в , ни в .Но нам нужно сделать обратное: из алгоритма, вычисляющего любоеполупрямое произведение мер , , согласованное с покомпонентным по­рядком, надо изготовить отделитель множеств , .

Для этого разберёмся,каким должно быть любое полупрямое произведение мер , , согласован­ное с покомпонентным порядком. Ключевую роль, здесь играет следующаялемма.48Лемма 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 = .Теперь мы можем доказать, что из любого алгоритма, вычисляющегонекоторое полупрямое произведение мер , , согласованное с покомпонент­ным порядком, можно изготовить отделитель множеств , .

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

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