6.2. m-полные множества

Теорема 32. Среди перечислимых множеств существу­ют наибольшие с точки зрения m-сводимости, то естьт-полные множества

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

<] Таковым является универсальное множество (фор­мально надо перейти от пар к их номерам). Пусть и С С N х N — перечислимое множество пар натуральных чисел, универсальное для класса перечислимых множеств натуральных чисел. Рассмотрим множество V номеров всех пар, входящих в и (для какой-то вычислимой нуме­рации пар (х,у) <->• [х, у] £Н). Другими словами,

V = {[х,у]\(х,у)еи}.

Пусть Т — произвольное перечислимое множество. То­гда Т = 11п при некотором п и потому

геГ«ш£[?„0 (п, х) £ 1Т О [п, х] £ V.

Таким образом, функция х н->- [п, х] сводит Т к V. >

Наибольшие относительно т-сводимости перечисли­мые множества называют га-полными (точнее, га-полны­ми в классе перечислимых множеств).

Заметим, что если К <Ст А для перечислимых мно­жеств К и А и при этом К является т-полным, то и А является т-полным (в силу транзитивности).

Если универсальное множество является главным, то его диагональ также т-полна:

Теорема 33. Пусть и С N х N — главное универсаль­ное множество для класса перечислимых множеств. То­гда его «диагональное сечение» О = {х | (х, х) £ 11} явля­ется т-полным.

(В частности, множество всех самоприменимых про­грамм является т-полным.)

<] Очевидно, О перечислимо. Пусть К — произволь­ное перечислимое множество. Рассмотрим перечислимое множество пар V = К х N. Его сечения Уп будут либо пусты (при а К), либо совпадать со всем N (при а £ е К).

Поскольку множество II является главным, существу­ет всюду определённая функция в, для которой Уп = = £/,(„). Другими словами, //,(„) совпадает с N при а £ Ки пусто при п К. Следовательно, в(п) £ ?78(п) (и пото­му в(п) £ О) при п £ К ж в(п) ^ ?78(п) (и потому в(п) (Ё I?) при п £ К. Таким образом, в сводит К к О. >

45. Докажите, что множество всех программ, останавли­вающихся на входе 0, является т-полным. Докажите, что мно­жество всех программ, останавливающихся хотя бы на одном входе, является т-полным.

46. Пусть М — т-полное перечислимое множество. По­кажите, что существует алгоритм, которой но номеру лю­бой всюду определённой функции Н указывает такое число и. что (п £ М) (Л(«) £ М). (Указание: это утверждение со­ставляет содержание теоремы о неподвижной точке для не­которого отношения эквивалентности.)