5.4. Несколько замечаний

Бесконечное множество неподвижных точек

Теорема 25 (о неподвижной точке) утверждает суще­ствование хотя бы одной неподвижной точки. Легко по­нять, что на самом деле их бесконечно много: в обозна­чениях этой теоремы существует бесконечно много чи­сел п, при которых 11п = и^(п)

Это можно объяснить, например, так: если бы непо­движных точек было бы конечное число, то можно было бы изменить функцию К в этих точках так, чтобы непо­движных точек не осталось. Недостаток этого рассужде­ния в том, что оно не позволяет эффективно перечислять неподвижные точки (указать для данной функции К бес­конечное перечислимое множество, состоящее из её непо­движных точек). Можно сделать и это, если вспомнить доказательство теоремы 25. В нём неподвижными точка­ми оказывались числа [<?](/), а функцию д можно выбрать так, чтобы все её значения были больше любого наперёд заданного числа (теорема 22, с. 36).

37. Проведите это рассуждение подробно.

Неподвижная точка с параметром

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

Теорема 28. Пусть и — главная универсальная функ­ция для класса вычислимых функций одного аргумента, а К — всюду определённая вычислимая функция двух аргу­ментов. Тогда существует всюду определённая вычисли­мая функция п одного аргумента, которая по любому р указывает неподвижную точку для функции /гр, так что ин(р,п(р)) = ип(р), или, другими словами,

и(Ь,(р,п(р)),х) = и(п(р),х)

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

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

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

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

38. Убедитесь, что приведённая в доказательстве теоре­мы 28 конструкция как раз и даёт функцию п(р) с таким свойством.

39. Объединяя сделанные выше замечания, покажите, что по любой вычислимой функции Л (заданной своим номером относительно фиксированной главной универсальной функ­ции) можно эффективно указать бесконечно много чисел, ка­ждое из которых либо будет неподвижной точкой для функ­ции Л, либо точкой, где эта функция не определена.

Неподвижная точка для перечислимых множеств

Всё сказанное почти без изменений переносится на главные нумерации перечислимых множеств (если Шг — главное универсальное перечислимое множество, то вся­кая вычислимая всюду определённая функция К имеет не­подвижную ТОЧКу П, ДЛЯ КОТОРОЙ ЦГп = ¥>ГЦп))-

В самом деле, если Шг — главное универсальное пере­числимое множество, то к отношению эквивалентности

а = Ь & Ша = Шь

применимо рассуждение из доказательства теоремы 25, поскольку любая вычислимая функция / имеет вычисли­мое всюду определённое =-продолжение.

Проверим это. Для этого рассмотрим множество

V = {(р, х) | f(p) определено и {/(р), х) £ ЦГ}.

Легко понять, что это множество перечислимо (напри­мер, оно есть область определения вычислимой функ­ции (р,х) I—У ш(/(р),ш), где IV — вычислимая функция с областью определения Шг). При этом Ур = ^г}(р), если f(p) определено, жУр = 0, если f(p) не определено. Вспо­миная, что Ш является главным универсальным множе­ством, мы находим всюду определённую функцию в, для которой Ур = И^р). Таким образом, ^(р) = ^}[р) Для тех р, для которых f(p) определено, что и требовалось.

40. Пусть IV — главное универсальное множество (для класса всех перечислимых подмножеств натурального ряда).

(а) Покажите, что найдётся число х, для которого IVх = {х}.

(б) Покажите, что найдутся различные числа х и у, для кото­рых \А/Х = {у} и №я = {х}.

Пример использования

Простейшее (хотя не очень типичное) применение теоремы о неподвижной точке — ещё одно доказатель­ство теоремы 21 о неразрешимости свойств вычисли­мых функций. В самом деле, пусть есть нетривиальное свойство Л вычислимых функций, которое можно рас­познавать по номерам функций в главной нумерации V. Пусть р — какой-то номер какой-то функции 11р, обла­дающей этим свойством, ад — какой-то номер какой-то функции      им не обладающим. Тогда функція д, если функция IIх обладает свойством Л, р, если функция 1}х не обладает свойством Л

будет вычислимой и не будет иметь неподвижной точки.

Изоморфизм универсальных множеств

Пусть 1}\ и V2 — два множества пар натуральных чисел. Мы будем называть их вычислимо изоморфными, если можно найти вычислимую перестановку (биекцию) г: N —5- N с таким свойством:

(х,у) <Е Щ     {г{х),г(у)) £ Щ.

Теорема 29. Любые два главных универсальных мно­жества для класса перечислимых подмножеств натураль­ного ряда вычислимо изоморфны.

<] Для начала объясним разницу между этой теоремой и теоремой об изоморфизме главных нумераций перечис­лимых множеств (см. замечание в конце раздела 4.3). Там мы применяли вычислимую перестановку только к но­мерам, но не к элементам множеств. В теперешних обо­значениях теорему об изоморфизме главных нумераций можно записать так:

(х,у) £ их О {г{х),у) £ и2.

Заметим, что вычислимая перестановка по второму ар­гументу сохраняет универсальность: если и С М2 —главное универсальное множество, а г: N —5- N — вычи­слимая перестановка, то множество пар (х,у), для кото­рых (х,1(у)) £ II, также является главным универсаль­ным множеством. Поэтому из теоремы об изоморфизме главных нумераций перечислимых множеств можно вы­вести такое следствие: для всякой вычислимой переста­новки г найдётся такая вычислимая перестановка г', что

(х,у) £ Щ     {г'{х),г(у)) £ £/2.

Если нам повезло и г' совпало с г, то перестановка г бу­дет требуемой. Мы хотим заменить везение ссылкой на теорему о неподвижной точке. На этом пути есть не­сколько препятствий, но все они преодолимы — и мы сейчас коротко опишем, как.

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

Сформулируем соответствующее обобщение теоремы об изоморфизме главных нумераций. Дадим предвари­тельно одно вспомогательное определение. Пусть /: N —У —5- N — произвольная функция. Будем говорить, что мно­жество А I-соответствует множеству В, если либо В есть образ А при отображении /, либо А есть прообраз В при этом отображении. (Если / — биекция, эти свойства равносильны.)

Пусть 1}\ и V2 — произвольные главные нумерации перечислимых множеств, а I: Н —5- N — вычислимая функция. Тогда существует такая вычислимая биекция г': N —У N, что при любом к множество с номером к в ну­мерации 1}\ /-соответствует множеству с номером г1 (к) в нумерации V2-

Это обобщение теоремы об изоморфизме главных ну­мераций доказывается так же, как и сама теорема, и но­мер функции г' может быть эффективно получен по номе­ру функции /. Это позволяет применить описанный план и найти биекцию /, при которой г' = /, что и требова­лось. >

41. Проведите это рассуждение подробно. Аналогичная теорема верна и для главных универ­сальных функций.

Теорема 30. Пусть Р\, Р2: N —У N — две главные уни­версальные функции для вычислимых функций одного аргумента. Тогда найдётся такая вычислимая переста­новка г, что

Рх(х, у) = г<$ Р2(і(х).,і(у)) = г'(-г)

для любых натуральных х, уж г.

42. Проведите доказательство этой теоремы но аналогии с предыдущей, используя теорему Роджерса об изоморфизме главных нумераций (с. 39, теорема 23).