6.3. т-полнота и эффективная неперечислимость

Теория алгоритмов позволяет, как говорят, «конст-руктивизировать» различные определения. В качестве примера возьмём определение бесконечного множества. Что такое бесконечное множество? Это множество, ко­торое содержит не менее п элементов для любого на­турального п. Теперь можно сказать так: множество называется «эффективно бесконечным», если существует алгоритм, который по любому п указывает п различных элементов этого множества.

47. Покажите, что произвольное множество А является эф­фективно бесконечным тогда и только тогда, когда оно содер­жит бесконечное неречислимое множество (т. е. не является иммунным, см. с. 22).

Сейчас нас будет интересовать эффективный вариант понятия неперечислимости. Что значит, что множест­во А неперечислимо? Это означает (трюизм), что А отли­чается от любого перечислимого множества. Естествен­но называть множество А эффективно неперечислимым, если по любому перечислимому множеству можно ука­зать место, где оно отличается от А.

Более формально, зафиксируем некоторое главное универсальное перечислимое множество Шг (и тем самым нумерацию перечислимых множеств: число п мы считаемномером множества Шп). Будем говорить, что множест­во А является эффективно неперечислимым, если суще­ствует такая всюду определённая вычислимая функция /, что f(z) Є А Д У/2 при всех г. (Здесь Д означает сим­метрическую разность; другими словами, f(z) является точкой, где А отличается от ¥/г.)

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

Свойство эффективной неперечислимости допускает простую характеризацию в терминах т-сводимости. На­чнём с такого простого наблюдения.

Теорема 34. Если А <^т В ж А эффективно неперечи-слимо, то и В эффективно неперечислимо.

<] Эта теорема является «эффективным вариантом» теоремы 31, часть (б). То же самое можно сказать и о её доказательстве. Пусть мы хотим найти точку, в ко­торой В отличается от некоторого перечислимого мно­жества X. Рассмотрим функцию /, которая т-сводит А к В. Прообраз /_1 (X) перечислимого множества X при вычислимом отображении будет перечислим, поэтому можно найти точку т, в которой он отличается от А. Тогда В отличается от X в точке f(m).

Чтобы сделать это рассуждение точным, нам нуж­но лишь доказать, что номер перечислимого множе­ства /_1 (X) может быть эффективно получен по номеру перечислимого множества X. Для этого мы должны вос­пользоваться тем, что нумерация является главной — схема тут та же, что и при вычислении номера ком­позиции двух вычислимых функций, заданных своими номерами (теорема 16). Проведём это рассуждение по­дробно.

Рассмотрим перечислимое множество

У = {{х,у) [ (х, /(у)) Є Ш}

(оно перечислимо, поскольку является прообразом пе­речислимого множества Шг при вычислимом отображе­нии {х,у) і—)- (х, /(у))). Легко видеть, что Уп = І~1{У^п).

Так как множество Шг является главным универсальным множеством, то существует вычислимая всюду опреде­лённая функция в, для которой ДО7,(п) = Уп = /~^(\№п) при всех п. Другими словами, функция в по И^-номе-ру любого перечислимого множества даёт И^-номер его прообраза при отображении /, что и требовалось. >

Теорема 35. Существуют перечислимые множества с эффективно неперечислимыми дополнениями.

<] Вновь рассмотрим диагональное множество О = = {п | (п,п) £ И7}. Его дополнение будет эффективно неперечислимым. В самом деле, множества Шгп и О оди­наково себя ведут в точке п, поэтому Цгп отличается от дополнения к О в этой точке. Таким образом, дополне­ние к О эффективно неперечислимо, причём в качестве функции / из определения эффективной неперечислимо­сти можно взять тождественную функцию. >

Из двух предыдущих теорем очевидно следует такое утверждение:

Теорема 36. Всякое т-полное перечислимое множест­во имеет эффективно неперечислимое дополнение.

На самом деле верно и обратное. Чтобы убедиться в этом, докажем такой факт:

Теорема 37. Пусть К — перечислимое множество, а А эффективно неперечислимо. Тогда N \ К <Ст А (или, что эквивалентно, К <Ст N \ А).

<] На самом деле нам важно умение эффективно от­личать А лишь от двух перечислимых множеств — от пустого и от всего натурального ряда. Отличить А от пу­стого множества означает указать элемент в А; отличить от всего натурального ряда означает указать элемент вне А. Именно эти две вещи используются при сведении. Более формально, рассмотрим множество V = К х N. Его сечения Уп либо пусты (при п К), либо совпадают со всем натуральным рядом (при п £ К). Пользуясь тем, что множество Шг является главным, мы находим всюду определённую функцию в, для которой ДО7,(п) = 0 при п £ £ К и ^(п) = N при п £ К. Пусть / — функция, обеспе­чивающая эффективную неперечислимость множества А. Тогда f(s(n)) £ А при п ^ К и f(s(n)) ^ А при п £ К.

Другими словами, композиция функций f Ш 8 сводит к множеству А, что и требовалось. >

Отсюда очевидно вытекают такие утверждения: Теорема 38. Перечислимое множество является т-пол­ным тогда и только тогда, когда его дополнение эффек­тивно неперечислимо.

Теорема 39. Множество эффективно неперечислимо тогда и только тогда, когда к нему т-сводится допол­нение некоторого (вариант: любого) т-полного множе­ства.

Отметим, что не всякое неперечислимое множество эффективно неперечислимо. Это видно, например, из та­кого факта:

Теорема 40. Любое эффективно неперечислимое мно­жество содержит бесконечное перечислимое подмноже­ство (т.е. не является иммунным).

<] В самом деле, пусть множество А эффективно непе­речислимо. Тогда отличим его от пустого множества — то есть найдём в нём элемент. После этого отличим его от одноэлементного множества, которое состоит из этого элемента — и найдём другой элемент. Действуя так, мы может алгоритмически найти сколь угодно много раз­личных элементов.

В этом рассуждении мы использовали такой факт: по конечному множеству, заданному списком его элементов, можно получить его номер (точнее, один из номеров) в главной нумерации перечислимых множеств. Почему это так? Пусть фиксирована некоторая вычислимая нумера­ция конечных множеств. Будем обозначать п-ое конеч­ное множество в этой нумерации через Оп. Тогда Оп бу­дет п-ым сечением перечислимого (и даже разрешимого) множества

В = {(п, х) | х 6 АЛ-

Остаётся воспользоваться определением главной нумера­ции перечислимых множеств. >

Простые множества, которые, как мы знаем, суще­ствуют (теорема 14), являются примерами перечислимых множеств, не являющихся т-полными. Именно так и воз­никло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы т-полным.