ВЫЧИСЛИМОСТЬ НА ВЕРОЯТНОСТНЫХ МАШИНАХ

В статье рассматривается следующий вопрос: имеются ли задачи, которые может решать машина со случайным элементом, но не может решать детерминистская машина?

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

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

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

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

Вероятностные машины в сравнении с детерминистскими

Начнем с точного определения некоторого класса вычислительных машин. Эти машины имеют вход и выход. Входом является бесконечная последовательность двоичных знаков, которая может подаваться двумя различными способами: 1) как фиксированная последовательность (физически можно представить заранее подготовленную бесконечную ленту); 2) как выход двоичного случайного устройства (с вероятностью появления 1). В последнем случае мы имеем вероятностную машину. Затем очертим точный класс задач, подлежащих решению на этих машинах, а именно перечисление с положительной вероятностью множеств выходных символов. После этого ключевой результат настоящей статьи — теорема 1— используется для получения подхода к ответу на наш вопрос. Ответ дается теоремой 2. Он гласит, что если случайное устройство имеет вероятность где — вычислимое действительное число (т. е. действительное число, для которого существует эффективный процесс нахождения любого знака в его двоичном разложении), то любое множество, перечислимое посредством вероятностной машины рассматриваемого типа, перечислимо посредством детерминистской машины. Это не справедливо, если — невычислимое действительное число. Аналогичные результаты получаются для случая, когда учитывается порядок следования выходных символов. Положение подытоживается теоремой 3.

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

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

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

1) есть начальный отрезок в

если есть начальный отрезок в

2) f — вычислимая функция, т. е. существует эффективный процесс, позволяющий определить по заданной

Это определение распространяется на бесконечные последовательности следующим образом: если то есть последовательность с начальными отрезками

Неформально работу машины можно представить себе следующим образом. Получив на входе она воспринимает и записывает последовательность символов на выходе; затем она воспринимает и записывает символы на ленте после производя затем она воспринимает и записывает символы на ленте после производя

и, наконец, останавливается.

Теперь дадим несколько конкретных примеров машин. Этим преследуется двоякая цель: проиллюстрировать наше понятие машины и подготовить материал для иллюстрации новых

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

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

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

Машина № 3. Пусть машина записывает символ 0, встретив первый нуль во входной последовательности. В остальное время она не записывает ничего. Тогда если один из символов является нулем. В противном случае машина не записывает ничего, и такая последовательность будет «пустой последовательностью»

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

Машина № 5. Пусть машина записывает выходной символ если максимальная длина групп единиц, воспринятых машиной, равна Например, .

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

Машина № 7. Эта машина задается соотношением где целое число

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

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

Если вводить в машину № I бесконечную ленту, на которой записаны только единицы, то выходная последовательность будет Для этой же ленты машина № 3 не даст никакого выхода [пустая последовательность ], а машина № 4 даст выходную последовательность (1).

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

Например, машина № 1 ставит в соответствие любой бесконечной входной последовательности множество выходных символов, состоящее из всех где пробегает целые положительные числа. Машина № 2 ставит в соответствие любой входной последовательности множество всех где пробегает целые положительные числа. Машина № 3 ставит в соответствие входной последовательности, состоящей только из единиц, пустое множество. Такому же входу машина № 5 ставит в соответствие множество всех целых положительных чисел.

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

символов называется А-перечислимым, если существует Л-машина, которая А-перечисляет это множество.

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

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

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

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

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

Лемма 3 и существование невычислимых последовательностей будут важны для нас позже.

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

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

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

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

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

Будет предложено два определения: определение -перечислимых множеств и определение сильно -перечислимых множеств. Наш первоначальный неформальный вопрос будет сведен к двум точным вопросам: каждое ли -перечислимое множество -перечислимо? Каждое ли сильно -перечислимое множество -перечислимо?

Остается дать эти два определения. Каждому множеству возможных выходных символов данной -машины можно приписать вероятность его появления в качестве полного выхода этой машины. Это есть вероятность того, что данное множество будет в точности множеством символов, которые появятся на выходной ленте машины, если машину привести в начальное положение, присоединить случайное устройство и пустить в работу. Указанная вероятность, конечно, равна нулю для большинства множеств. Дадим несколько примеров, ссылаясь на описанные выше машины. Предположим, что они присоединены к случайному устройству с и стали поэтому -машинами. Машина № 1 перечисляет любое множество с нулевой вероятностью. Следует отметить, что конечные множества появиться не могут, и по этой причине они имеют нулевую вероятность. Хотя некоторые бесконечные множества и могут быть выходом, однако это случается лишь с нулевой вероятностью. Не следует забывать о различии между появлением с нулевой вероятностью и невозможностью появления. Машина № 2 перечисляет множество всех с вероятностью 1 (и притом с достоверностью). Выход машины № 3 есть множество, состоящее из единственного символа 0, с вероятностью 1, но без достоверности. Выход машины № 5 есть множество всех целых положительных чисел — с вероятностью 1, но без достоверности, ибо бесконечная последовательность нулей и единиц содержит произвольно длинные

группы единиц с вероятностью 1, но без достоверности. Машина № 6 перечисляет с вероятностью множество всех где фиксировано, а пробегает все целые положительные числа. Иными словами, машина вычисляет функцию [определяемую соотношением с вероятностью .

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

Предыдущие примеры показывают, что следующие множества сильно -перечислимы: множество всех — множество, состоящее только из 0; множество целых положительных чисел; множество всех с фиксированным

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

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

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

перечислит в точности что все это остается справедливым, если в определении взять вместо 1/2 большее число. Остаются справедливыми и все последующие результаты.)

Определение. Множество символов называется -перечислимым, если существует такая машина М, что есть в точности

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

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

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

Теперь для любого числа между 0 и 1 у нас есть три понятия: -перечислимости, -перечислимости и сильной -перечислимости. Из них лишь первое понятие является строго детерминистским, тогда как остальные — вероятностными.

Основной результат формулируется следующим образом.

Теорема 1. Яусть — множество символов, — действительное число, Три следующих предложения эквивалентны:

1) является А -перечислимым;

2) является -перечислимым;

3) является сильно -перечислимым.

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

Пусть — невычислимое действительное число между 0 и 1. Известно, что такие числа существуют и что в действительности почти все (в смысле меры Лебега) числа невычислимы.

Невычислимость эквивалентна невычислимости Тогда в силу леммы 3 существует множество которое -перечислимо, но не -перечислимо. В силу теоремы 1 это множество как -перечислимо, так и сильно -перечислимо, но не -перечислимо. Следовательно, если имеются случайные устройства, записывающие символ 1 с вероятностью, которая не является вычислимым действительным числом, то можно построить -машины, которые будут «перечислять» множества, не являющиеся -перечислимыми.

Положение совершенно меняется в случае, когда есть вычислимое действительное число (в частности, когда оно равно 1/2). Это равносильно вычислимости последовательности Теорема 1 показывает, что любое -перечислимое или сильно -перечислимое множество должно быть А -перечислимым. Так как А -вычислимо, то по лемме 2 рассматриваемое множество должно быть -перечислимым. Следовательно, -перечислимое или сильно -перечислимое множество должно быть -перечислимым. Отсюда вывод, что если в качестве брать только вычислимые действительные числа (в частности, 1/2), то машина со случайным устройством не сможет «перечислить» ничего сверх того, что перечисляет детерминистская машина.

Оба случая охватывает следующая теорема.

Теорема 2. Если — вычислимое действительное число, то любое -перечислимое или сильно -перечислимое множество -перечислимо., Если —невычислимое действительное число, то существуют -перечислимые и сильно -перечислимые множества, не являющиеся 1-перечислимыми.

Дадим набросок доказательства теоремы 1. Доказательство состоит из вывода предложения 2 из предложения 3, вывода предложения 1 из предложения 2 и вывода предложения 3 из предложения 1. Эта цепочка заключений дает требуемую эквивалентность.

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

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

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

То, что 1 влечет 3, доказывается следующим образом. Строится -машина, вычисляющая с вероятностью большей 1/2 двоичное разложение действительного числа или выход машины есть (с вероятностью большей 1/2) множество всех где есть знак в двоичном разложении числа Машина, делающая это, является видоизменением машины № 7. Если выход этой -машины использовать как вход другой машины М, то выход последней будет с вероятностью большей 1/2 в точности таким, каким был бы выход машины М, имеющий в качестве входа последовательность Если есть любое -перечислимое множество и М — машина, А перечисляющая его, то построенная выше сложная машина есть -машина, сильно -перечисляющая Следовательно, любое -перечислимое множество сильно -перечислимо. Это доказывает, что 1 влечет 3, и набросок доказательства теоремы 1 Тем самым закончен.

Исследуем теперь, останутся ли результаты теми же, если учитывать не только совокупность выходных символов, но и порядок их следования. Будет показано, что такое положение можно свести к частному случаю уже полученных результатов.

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

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

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

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

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

Из двух предыдущих лемм и теоремы 2 вытекает лемма 6.

Лемма Пусть — вычислимое действительное число частности, 1/2). Тогда любая -вычислимая или сильно -вычислимая последовательность -вычислима.

Доказательство. Пусть последовательность будет -вычислима или сильно -вычислима. Тогда -перечислимо или сильно -перечислимо по лемме 5. По теореме 2 множество будет -перечислимо. По лемме 4 последовательность должна быть -вычислимой.

Это охватывает случай, когда — вычислимое действительное число. Если невычислимо, то доказательство теоремы 1, данное в приложении, показывает, что существует -вычислимая и сильно -вычислимая, но не -вычислимая последовательность (эта последовательность представляет собой двоичное разложение числа Объединяя оба случая, получим следующий аналог теоремы 2 для понятий вычислимости.

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

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

Более общий класс машин

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

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

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

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

Любой -машине М можно поставить в соответствие стохастическую машину в указанном выше смысле. Состояния соответствующей стохастической машины суть конечные последовательности нулей и единиц а начальное состояние — «пустая» последовательность (Фактически «состоянием» -машины называют входную последовательность, воспринятую ею. Эти «состояния» могут не соответствовать возможным внутренним состояниям конкретной машины, но определяют их полностью.) Вероятность перехода из состояния есть а из состояния есть Соответствующая стохастическая машина записывает по приходе в состояние то же, что и -машина, принявшая входной символ после восприятия Тем самым стохастическая машина полностью задана. Она будет в дальнейшем называться стохастической машиной, соответствующей -машине М. Таким образом, -машины можно отождествить с частными случаями стохастических машин. Легко видеть, что если — вычислимое число, то соответствующая стохастическая машина обладает следующим специальным свойством: функция Р вычислима, т. е. существует эффективный процесс, позволяющий по заданному целому положительному числу т. состояниям и выходному символу вычислить первые знаков двоичного разложения

Назовем стохастические машины с таким свойством вычислимо стохастическими машинами (или в.с.-машинами). Непосредственным следствием этих определений является следующая лемма.

Лемма 7. Стохастическая машина, соответствующая -машине, является в.с.-машиной тогда и только тогда, когда — вычислимое действительное число.

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

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

Определение. Два объекта — стохастические машины или -машины — будут называться эквивалентными, если для любого конечного множества символов они имеют одинаковую вероятность включения (в конце концов) этого множества в их выход. Если эти машины суть то их эквивалентность будем обозначать так:

Например, -машина и соответствующая ей стохастическая машина эквивалентны.

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

есть множество символов, которое перечисляет машина М. Как непосредственное следствие из нашего определения эквивалентности получаем, что влечет Две эквивалентные машины перечисляют одно и то же множество.

Определение. Множество в. -перечислимо, если существует такая в.с.-машина М, что

Теперь ответим на вопрос: каждое ли в.с.-перечислимое множество -перечислимо? Ответ вытекает из следующего утверждения, доказанного в приложении.

Теорема 4. Каждая в.с.-машина эквивалентна -машине.

Следовательно, если М есть в.с.-машина, то множество которое перечисляет машина М, перечислимо также некоторой -машиной. По теореме 2 множество должно быть -перечислимым. Отсюда вытекает следующее утверждение.

Теорема 5. Любое в.с.-перечислимое множество -перечислимо.

Этот результат и был упомянут выше.

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

Теорема 4 (дополнение). Существует эффективный процесс, позволяющий по заданному описанию в.с.-машины получить описание эквивалентной ей -машины.

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

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

Из объединения дополнений теорем 1 и 4 следует теорема 5.

Теорема 5 (дополнение). Существует эффективный процесс, позволяющий по заданному описанию в.с.-машины, в.с.-перечисляющей множество получить описание -машины, которая -перечисляет

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