7.1. Машины с оракулом

Если множество В m-сводится к разрешимому мно­жеству А, то ж В разрешимо. Более того, если даже А ж неразрешимо, но у нас есть доступ к «оракулу» для А, ко­торый отвечает на вопросы о принадлежности чисел мно­жеству А, то мы можем с его помощью отвечать на во­просы о принадлежности чисел множеству В. В самом де­ле, если / — сводящая функция и если мы хотим узнать, принадлежит ли некоторое число х множеству В, доста­точно спросить у оракула, принадлежит ли f(x) множе­ству А.

Легко видеть, что m-сводимость использует возмож­ности оракула довольно ограниченным образом: во-пер­вых, оракулу задаётся только один вопрос, во-вторых, ответ на этот вопрос и считается ответом на исходный вопрос о принадлежности числа х множеству А. Вот при­мер, не укладывающийся в такую схему: имея оракул для множества А, мы можем отвечать на вопросы о при­надлежности чисел множеству В = N \ А. Здесь вопрос по-прежнему один, но ответ на него заменяется на про­тивоположный. Другой пример: имея оракул для множе­ства А, можно отвечать на вопросы о принадлежности пары натуральных чисел множеству В = А х А. (Здесь оракулу надо задать уже два вопроса.)

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

Машины с оракулом

Этот вид сводимости называется сводимостью по Тьюрингу, или Г-сводимостью. Обозначение: В <Ст А означает, что В сводится по Тьюрингу к А. Вот несколь­ко простых фактов про Г-сводимость:

Теорема 43. (а) Если В ^т А, то В       А. (б) А М\А при любом А. (в) Если А       В и В С, то А <Ст С. (г) Если А <Ст В ж В разрешимо, то А разре­шимо.

<] Все эти утверждения почти очевидны — поясним, например, утверждение (в). Пусть у нас есть алгоритм для А, включающий вызовы внешней разрешающей про­цедуры для В, а также алгоритм для В, включающий вы­зовы внешней процедуры для С. Тогда можно заменить вызовы внешней В-процедуры на этот второй алгоритм и получится разрешающий алгоритм для А, использую­щий вызовы внешней процедуры для С. >

Заметим, что (в отличие от т-сводимости) неперечи-слимое множество вполне может Г-сводиться к перечи­слимому. Например, дополнение перечислимого неразре­шимого множества К сводится к самому множеству К.

Можно говорить не только о сводимости к множе­ству А, но и вообще об алгоритмах, имеющих доступ к оракулу для множества А. Пусть такой алгоритм вычи­сляет некоторую функцию /. Это означает, напомним, что если f(x) определено, то на входе х алгоритм оста­навливается и даёт ответ f(x), а если f(x) не определе­но, тоне останавливается. (Предполагается, естественно, что оракул «не зависает» и выдаёт ответы, притом пра­вильные, на все заданные ему вопросы.) В этом случае говорят, что (частичная) функция / вычислима относи­тельно множества А.

В нашем определении сводимости вызываемая внеш­няя функция принимала только два значения («да» и «нет»). Такое ограничение вовсе не обязательно. Пусть а : N —У N — произвольная всюду определённая функция. Тогда можно говорить о функциях, вычислимых относи­тельно а; вычисляющие их алгоритмы включают в себя вызовы функции а. Однако это обобщение не является существенным:

Теорема 44. Частичная функция / вычислима отно­сительно всюду определённой функции а тогда и толь­ко тогда, когда она вычислима относительно множества, являющегося графиком функции а, то есть относительно множества {(п, а(п)) \ п Є М}.

<] В самом деле, если мы можем вызывать функцию а, то можем и отвечать на вопросы о принадлежности про­извольной пары графику функции а. Напротив, если мы можем разрешать график а, то можем найти а(х) для данного х, задавая по очереди вопросы о принадлежно­сти графику пар (х, 0), (х, 1),..., пока не получим поло­жительный ответ. >

Определяя вычислимость относительно функции а, мы предполагали, что а всюду определена. Это ограниче­ние принципиально: для не всюду определённых функций механизм обращения к ним (как к внешним процедурам) требует уточнений. Допустим, мы вызвали а(х), а оказа­лось, что функция а не определена на х. Означает ли это, что алгоритм в этом месте «зависает» и уже не может выдать результат? Или мы можем параллельно развер­нуть какие-то вычисления и в каких-то случаях выдать результат, не дожидаясь ответа от а(х)1 Можем ли мы параллельно запросить несколько значений функции а? Например, следует ли считать функцию f(x), заданную формулой 0, если а(2х) или а(2х + 1) определено не определено в противном случае

вычислимой относительно а? Короче говоря, в отличие от случая всюду определённых функций, тут есть разные (и притом не эквивалентные) варианты определений, и всегда надо уточнять, какое именно понятие имеется в виду. Поэтому мы, говоря о вычислимости относитель­но некоторой функции а, предполагаем, что функция а всюду определена.

58. Пусть есть два различных множества X и У". Будем рассматривать программы, имеющие доступ к двум ораку­лам для X и для У", и функции, которые можно вычислить с

Эквивалентное описание

помощью таких программ. Покажите, что это определение не даёт ничего существенно нового, указав такое множество И, что Х-У-вычислимость совпадает с ^-вычислимостью.