6.5. Продуктивные множества

В этом разделе мы используем теорему о неподвиж­ной точке для получения такого (неожиданного на пер­вый взгляд) результата: определение эффективной непе­речислимости множества А не изменится, если мы огра­ничимся лишь (перечислимыми) подмножествами множе­ства А.

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

№„СА^/(п)еА\№„.

48. Докажите, что продуктивное множество не может быть иммунным.

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

Теорема 42. Пусть А — продуктивное множество, К — произвольное перечислимое множество. Тогда до­полнение к К т-сводится к А.

(Из этого следует, что А является эффективно непе-речислимым, см. выше.)

<] Пусть / — функция, которая существует по опре­делению продуктивности (и даёт элемент вне подмноже­ства с указанным номером).

Мы построим всюду определённую вычислимую фун­кцию в с такими свойствами:

• х £ К =>• Ш^х) = 0;

• х е К => = {f(s(x))}.

(второе свойство подразумевает, что f(s(x)) определено при х £ К). Прежде чем делать это с помощью теоре­мы о неподвижной точке, заметим, что в первом случае f(s(x)) определено и принадлежит А: поскольку множест­во с номером в(а;) пусто и является подмножеством А, число f(s(x)) должно быть элементом А. Напротив, во втором случае f(s(x)) не принадлежит А. В самом деле, если бы это было не так, то множество ДО7,(яг) было бы под­множеством А, и потому число f(s(x)) должно было быбыть элементом А, не входящим в это подмножество — а оно входит.

Поэтому если нам удастся построить такую функ­цию s, то функция х и-)- f{s(x)) будет m-сводить допол­нение множества К к множеству А, как мы и обещали. Как же её строить?

Если бы во втором свойстве (для х £ К) стояло не f(s(x)), а, скажем, просто f(x), никакой проблемы бы не было. Как обычно, мы рассмотрели бы перечисли­мое множество пар

V = {(х, у) | х £ К и у = f(x)};

сечения этого множества имели бы требуемый вид и осталось бы только воспользоваться тем, что нумера­ция — главная. Но в нашем случае, когда в правой части второго свойства стоит f(s(x)), так просто поступить нельзя: как в истории о курице и яйце, для построения V нам надо иметь s(x), а для построения s(x) надо иметь V.

Именно такого рода трудности позволяет преодоле­вать теорема о неподвижной точке. Построим всюду определённую вычислимую функцию двух аргументов h с такими свойствами:

• х £ К => Wh{Xit) = 0;

• х Е Wh{x>t) = {/(<)}.

(Подобные вещи мы делали многократно — последний раз в предыдущем абзаце. Отметим, что f(i) может быть и не определено, тогда под {f(t)} мы понимаем пустое множество.) По теореме о неподвижной точке (для пере­числимых множеств) при каждом х функция t н->- h(x,i) имеет неподвижную точку, и, как мы говорили в раз­деле о неподвижной точке с параметром, эту неподвиж­ную точку можно выбрать вычислимо зависящей от х. Таким образом, существует всюду определённая вычи­слимая функция s, для которой

Ws(x) = Wh(x,s(x))при всех х. Это равенство можно продолжить:

0, если х £ К,

ws(x) - wh{xAx)) - {{fis{x))h если х е к

— это ровно то, чего мы и хотели. Заметим, что значе­ние f(s(x)) определено при всех х (иначе Ws(x) = 0, и f(s(x)) должно быть определено). Тем самым, теорема о неподвижной точке позволяет отыскать взаимно согла­сованные яйцо и курицу и завершает доказательство. > Перечислимые множества, дополнения которых про­дуктивны, называются креативными (creative; иногда это слово переводят как «творческие»). Название объ­ясняется так: это множество (точнее, его дополнение) более изобретательно, чем любой алгоритмический про­цесс: если кто-то предлагает способ порождать некото­рые элементы из дополнения, то в ответ можно указать элемент дополнения, который нельзя получить таким способом.

Как мы видим, творческие множества, перечислимые множества с эффективно неперечислимым дополнением и m-полные множества — один и тот же класс, и любые два множества из этого класса в некотором смысле изо­морфны (отличаются лишь вычислимой перестановкой).

Если множество продуктивно, то можно порождать его элементы следующим индуктивным процессом. На первом шаге имеется пустое множество. Применив к не­му продуктивную функцию (т. е. функцию, существую­щую по определению продуктивного множества), мы по­лучим некоторый элемент. Он образует одноэлементное подмножество. Применив к этому подмножеству продук­тивную функцию, получим другой элемент. К получен­ному двухэлементному подмножеству можно снова при­менить продуктивную функцию и так далее. Получит­ся бесконечная вычислимая последовательность элемен­тов продуктивного множества. (Это мы уже делали, ко­гда доказывали, что эффективно неперечислимое мно­жество содержит бесконечное перечислимое подмноже­ство.) Но этот индуктивный процесс можно «трансфи­питно» продолжить, по крайней мере ещё немного: имея перечислимое подмножество нашего продуктивного мно­жества (множество членов последовательности), можно найти ещё один элемент продуктивного множества (так сказать, элемент номер и>). Добавим его к последователь­ности, снова применим продуктивную функцию, полу­чится (и> + 1)-ый элемент и так далее, затем получится новая последовательность, (и>'2)-ът элемент, (и>3)-ый, ... , о;2-элемент и т. д.

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

49. Не используя теорему о неподвижной точке (и тео­рему 42), покажите, что для всякого продуктивного множе­ства А существует всюду определённая вычислимая функ­ция /, для которой И С А влечёт ]'(п) £ А \ И . (Указание: чередуйте И с пустым множеством, как это делается при доказательстве леммы к теореме 41.)