Приложение

Лемма 1. Последовательность А вычислима тогда и только тогда, когда соответствующее множество А -перечислимо.

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

Лемма 2. Если А есть вычислимая последовательность, то любое А-перечислимое множество -перечислимо (и обратно).

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

Лемма 3. Если А является невычислимой последовательностью, то существуют А-перечислимые множества, которые не являются -перечислимыми.

Доказательство. Множество А является таким множеством. Теперь формализуем понятие случайного устройства. Пусть D — множество всех бесконечных последовательностей из нулей и единиц. Пусть подмножество D, состоящее из всех последовательностей, которые начинаются с Будем рассматривать D как измеримое пространство [5], в котором классом измеримых множеств является -кольцо [51, порожденное множествами Пусть М — машина (точное определение машины уже было дано) и — множество возможных выходных символов машины М.

Пусть множество всех конечных или бесконечных последовательностей элементы которых входят в 5. Будем рассматривать как измеримое пространство, в котором классом измеримых множеств является -кольцо, порожденное множествами и конечными последовательностями. Пусть множество всех подмножеств в 5 и, кроме того, пусть — подмножество в состоящее из всех подмножеств в содержащих и не содержащих Рассмотрим как измеримое пространство, в котором классом измеримых множеств является -кольцо, порожденное множествами Е.

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

Из этих определений непосредственно следует лемма.

Лемма. Отображения и км сохраняют измеримость.

Пусть — действительное число, можно рассматривать как пространство выборки случайного устройства, записывающего единицы с вероятностью и нули с вероятностью Иными словами, D есть пространство всех возможных событий, какие могут произойти, если наблюдать бесконечно много независимых операций случайного устройства. Каждому естественным образом соответствует мера на D, приписывающая каждому измеримому подмножеству в D вероятность того, что случайное устройство запишет бесконечную последовательность из этого подмножества. Поэтому индуцирует обычным образом вероятностные меры на пространствах Каждому измеримому подмножеству Е в приписывается вероятность а каждому измеримому подмножеству в приписывается вероятность Эти индуцированные меры будем обозначать через а иногда через Из контекста всегда будет ясно, какая мера используется.

Значение мер ты, Р очевидно. Если Е есть измеримое подмножество в то представляет вероятность того, что выходная последовательность машины М входит в Е, когда М работает как -машина. Если — измеримое подмножество в то — вероятность того, что множество выходных символов, перечисляемых М, есть элемент из когда машина работает как -машина.

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

Теперь дадим доказательство теоремы 1. Сначала докажем, что 3 влечет 2, т. е. что сильно -перечислимое множество должно быть -перечислимым.

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

Построим машины описываемые так: выход машины в ответ на вход такой же, как и выход машины М в ответ на вход Следовательно, машина действует в своем начальном состоянии так же, как если бы она была машиной М, уже воспринявшей вход Интуитивно представляется довольно правдоподобным, что если множество есть выход с положительной вероятностью машины М, то существуют машины выход которых есть с вероятностью, сколь угодно близкой к 1. [Такую можно было бы взять в качестве М и тем самым завершить доказательство того, что 3 влечет 2.] Подтверждается это так. Пусть есть т. е. подмножество в D, состоящее из всех последовательностей, дающих на выходе множество если сделать их входом машины М. Так как М производит с положительной вероятностью, то Вспомним, что есть подмножество в D, состоящее из всех последовательностей с начальным отрезком Вероятность того, что будет выходом равна

Следовательно, наша цель будет достигнута, если удастся найти такие последовательности чтобы

было произвольно близко к 1. В действительности справедливо более сильное утверждение.

Лемма. Пусть — некоторая последовательность в D. Тогда для всех В в D, кроме множества меры нуль,

существует и равен 1 для каждой последовательности из и равен 0 для каждой последовательности вне

Для доказательства этой леммы установим сохраняющее меру соответствие между пространством D с мерой и единичным интервалом I с мерой Лебега и воспользуемся следующим результатом о мере Лебега являющимся точным аналогом нашей леммы.

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

существует и равен 1 для х в и равен 0 для х вне

Соответствие устанавливается так. Пусть отображение задается формулой

где Образ каждой бесконечной последовательности есть действительное число, двоичным разложением которого является эта последовательность. Отображение есть отображение «на» и взаимнооднозначно, кроме счетнрго множества точек. Отображение и мера индуцируют меру на I. Если то есть обычная мера Лебега и — искомое соответствие. При надо сделать еще шаг. Пусть задается посредством равенства где — замкнутый интервал от 0 до х. Ясно, что есть отображение «на», взаимнооднозначно, монотонно и непрерывно в обе стороны. Пусть есть сложное отображение, составленное из Это есть искомое соответствие. Его свойства таковы.

1) если Е — измеримое подмножество в D, то есть измеримое по Лебегу подмножество в

2) если — последовательность в D, то есть интервал, содержащий точку из I.

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

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

После этого докажем, что 2 влечет 1, т. е. что -перечислимое множество должно быть А -перечислимым.

Пусть любое действительное число, Пусть М — любая -машина. Для доказательства того, что 2 влечет 1, достаточно будет построить машину, -перечисляющую (множество, -перечисляемое машиной М).

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

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

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

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

Далее докажем, что 1 влечет 3, т. е. что -перечислимое множество должно быть сильно -перечислимым.

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

Теперь построим машину М со следующим свойством 1). Пусть — действительное число, имеющее бесконечное двоичное разложение. Если выход случайного устройства, записывающего 1 с вероятностью подвести к М, то на выходной ленте машины М будет записано с вероятностью двоичное разложение числа (Выбор числа 3/4 несуществен. Оно может быть заменено всюду в дальнейшем любым

Пусть — машина, А -перечисляющая Если выходная лента машины М, соединенной со случайным устройством, имеющим вероятность служит входом в то выход сложной машины есть с вероятностью большей 3/4 множество Сложная машина есть -машина, сильно -перечисляющая множество Следовательно, если можно построить М, то будет доказано, что любое -перечислимое множество сильно -перечислимо. Тем самым будут охвачены оба случая: когда — конечная двоичная дробь и когда бесконечная двоичная дробь, так что достаточно построить такук машину М.

Пусть такая вычислимая последовательность рациональных чисел, что

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

Точное построение таково. Пусть есть координатная функция на D. Это значит, что при

Будем рассматривать D как множество всех возможных выходных последовательностей случайного устройства.

Число единиц, появившихся во время первых операций устройства, и доля этих единиц суть соответственно

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

Определим функцию следующим образом:

для всех целых положительных и всех и всех Это вероятность того, что случайное

устройство, имеющее вероятность запишет последовательность символов, в которой доля единиц отклоняется от более чем на Легко видеть, что — рациональное число и что функция вычислима. Заметим, что и потому функция которую мы определим как

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

Лемма,

Доказательство. Теорема из работы [4] (стр. 145) показывает, что при

отсюда при

и, в частности,

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

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

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

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

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

и, следовательно, существует такое единственное что для всех достаточно больших будет Но тогда

По усиленному закону больших чисел [4] для каждого А, кроме множества -меры нуль,

Так как есть бесконечная двоичная дробь, то она не равна ни одному Следовательно,

Так как вероятность того, что не определена, равна О, то вероятность того, что первые знаков в правильны, равна 1 минус вероятность того, что среди первых знаков в есть неправильный. Поэтому достаточно вычислить последнюю вероятность. Она равна

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

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

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

определена только тогда, когда существует такое что Следовательно,

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

Повторяем, что 3/4 можно заменить любым X, для которого и что построение остается тем же для всех с бесконечным двоичным разложением. Поэтому справедливо следующее. Для любого существует такая машина что если использовать как -машину, где — любая бесконечная двоичная дробь, то выход машины есть двоичное разложение с вероятностью большей .

Лемма есть -вычислимая последовательность тогда и только тогда, когда есть -перечислимое множество.

Доказательство. Такое же, как для леммы 1.

Лемма 5. Если сильно -вычислима, то сильно -перечислимо. Если -вычислима, то -перечислимо.

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

Пусть М — стохастическая машина. Пусть — множество всех последовательностей элементы которых суть названия состояний машины М. Пусть — множество всех последовательностей с начальным отрезком Будем рассматривать как измеримое пространство, в котором классом измеримых множеств является -кольцо, порожденное множествами Стохастический процесс, лежащий в основе машины, естественно, определяет меру на которая сопоставляет каждому измеримому множеству вероятность прохождения машины через некоторую последовательность состояний этого множества. Пусть — множество возможных выходных символов машины М. Как и прежде, суть соответственно множество всех последовательностей элементов из и множество всех подмножеств Отображение ставит в соответствие каждой бесконечной последовательности состояний выходную последовательность, записываемую, когда машина проходит через эту последовательность состояний. Соединение

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

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

Лемма. Если то совпадают на всех множествах вида

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

где слагаемые не пересекаются. совпадают на первых двух множествах и потому должны совпасть на третьем.

Множество всех подмножеств в вида есть кольцо множеств и порождает -кольцо множеств. Следовательно, если совпадают на кольце, то они совпадают и на всех измеримых множествах в [5, стр. 54]. Справедливость обратного очевидна, что влечет лемму.

Лемма. тогда и только тогда, когда

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

Чтобы доказать теорему 4 об эквивалентности каждой стохастической машины некоторой -машине, нужен еще один шаг

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

Определение. Стохастическая машина называется марковской, если:

1) не зависит от

2) для каждого существует единственное для которого

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

Лемма. Каждая стохастическая машина М эквивалентна некоторой марковской стохастической машине М. Если М есть в.с.-машина, то в качестве М можно выбрать в.с.-машину.

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

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

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

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

Заметим, что и что

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

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

Если

(что произойдет с вероятностью 1), то в конечном счете придем к первому такому, что

Тогда записываем 1, если

и 0, если справедливо обратное неравенство. Так как

в точности с вероятностью и

с вероятностью то событие «записана 1» появляется с вероятностью а событие «записан 0» — с вероятностью (Заметим, что событие «ничего не случилось» происходит с вероятностью 0, но все же возможно.) Повторим этот процесс. Описанный объект есть устройство, записывающее 1 с вероятностью

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

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

лежит между

и

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

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

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

на этот раз с первыми значениями вычисленными машиной С вероятностью 1 эти сравнения в конце концов дадут целое число такое, что

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

Доказательство теоремы 4 завершено.

ЛИТЕРАТУРА

(см. скан)

(см. скан)