5.1. Неподвижная точка и отношения эквивалентности

Теорема 25. Пусть U — главная вычислимая универ­сальная функция для класса вычислимых функций одно­го аргумента, a h — произвольная всюду определённая вычислимая функция одного аргумента. Тогда существу­ет такое число п, что Un = £//,(„), то есть п и h(n) — номера одной функции.

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

<] Мы будем действовать по аналогии с построением вычислимой функции, не имеющей всюду определённого вычислимого продолжения (глава 2).

Рассмотрим произвольное отношение эквивалентно­сти (которое мы будем обозначать х = у) на множе­стве натуральных чисел. Мы покажем, что следующие два свойства этого отношения не могут выполняться од­новременно:

• Для всякой вычислимой функции / существует всю­ду определённая вычислимая функция д, являюща­яся её =-продолжением (это означает, что если f(x) определено при некотором х, то д(х) = f(x)).

• Существует всюду определённая вычислимая функ­ция h, не имеющая =-неподвижной точки (то есть функция, для которой п ^ h(n) для всех п).

Если х = у — отношение равенства (х = у), то второе свойство выполнено (положим, например, h(n) = п + 1), поэтому не выполнено первое. Теорема о неподвижной точке получится, если х = у понимать как Ux = Uy (х ту — номера одной и той же функции). В этом случаевыполнено первое свойство, как мы сейчас убедимся, и потому не выполнено второе.

Почему выполнено первое свойство? Пусть / — произ­вольная вычислимая функция одного аргумента. Рассмо­трим функцию V(n,x) = U(f(n),x). Поскольку U явля­ется главной универсальной функцией, найдётся всюду определённая функция s, для которой V(n, х) = U(s(n), х) при всех п и х. Эта функция и будет искомым ^-продол­жением. В самом деле, если f(n) определено, то s(n) будет другим номером той же функции, что и f(n). (Отметим, что если f(n) не определено, то s(n) будет одним из но­меров нигде не определённой функции.)

Для завершения доказательства теоремы о неподвиж­ной точке осталось проверить, что указанные два свой­ства отношения эквивалентности несовместны. Это де­лается так же, как в теореме 9 (раздел 2.2). Возьмём вы­числимую функцию /, от которой никакая вычислимая функция не может отличаться всюду (например, диаго­нальную функцию х и-)- и(х,х) для некоторой вычисли­мой универсальной функции U). По предположению су­ществует всюду определённое вычислимое ^-продолже­ние g функции /. Рассмотрим функцию i(x) = h(g(x)), где h — вычислимая всюду определённая функция, не имеющая =-неподвижной точки. Тогда t будет всюду от­личаться от /. В самом деле, если f(x) определено, то f(x) = g(x) ^ h(g(x)) = i(x), и потому f(x) ф i(x). Ес­ли же f(x) не определено, то этот факт сам по себе уже отличает f(x) и i(x). >

Теорему о неподвижной точке можно переформули­ровать и так:

Теорема 26. Пусть U(п, х) — главная вычислимая уни­версальная функция для класса вычислимых функций од­ного аргумента. Пусть V(n, х) — произвольная вычи­слимая функция. Тогда функции U и V совпадают на некотором сечении: найдётся такое р, что Up = Vp, то есть U(р, п) = V(p, п) для любого п.

<] Так как функция U является главной, найдём такую всюду определённую вычислимую функцию h, что V(n,x) = U(h(n),x) при всех п и х. Осталось взятьв качестве р неподвижную точку функции К. >

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

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

Рассуждение начинается с рассмотрения «диагональ­ной» функции и(х,х), которую теперь можно записать как [ж](ж) (результат применения программы ж к себе). Далее мы строим её всюду определённое ^-продолже­ние. Это делается так. Выражение [[ж] (ж)] (у) вычисли­мо зависит от двух аргументов. Мы вспоминаем, что 1} есть главная универсальная функция, и находим та­кую программу д, что [[?](ж)](у) = [[ж] (ж)] (у) при всех ж и у. При этом [<?](ж) определено для всех х. Пусть мы хотим найти неподвижную точку программы К. Мы рас­сматриваем композицию [Л]([<?](ж)). Это выражение вы­числимо зависит от ж, и потому существует програм­ма I, для которой Щ(х) = [Л]([(?](ж)) при всех х. Эта программа применима ко всем х, поскольку таковы К и д. Теперь неподвижной точкой будет [<?](/). Чтобы убе­диться в этом, мы должны проверить, что [[<?](/)] (х) = = [И([?](^))](ж) Лля всех х- В самом деле, по свойству д имеем [[<?](/)] (х) = [[/](/)] (х). Вспоминая определение I, это выражение можно переписать как [[^]([?](^))](ж) — что как раз и требовалось.