Теорема о неподвижной точке

напечатать два раза, второй раз в кавычках, такой текст:
"напечатать два раза, второй раз в кавычках, такой текст:"

program selfprint;
 var a:array[1..100]of string;i:integer;
begin
a[1]:='program selfprint;';
a[2]:=' var a:array[1..100]of string;i:integer;';
a[3]:='begin';
a[4]:='for i:=1 to 3 do writeln(a[i]);';
a[5]:='for i:=1 to 11 do begin';
a[6]:='  write(chr(97),chr(91),i);';
a[7]:='  write(chr(93),chr(58),chr(61));';
a[8]:='  writeln(chr(39),a[i],chr(39),chr(59));';
a[9]:='end;';
a[10]:='for i:=4 to 11 do writeln(a[i]);';
a[11]:='end.';
for i:=1 to 3 do writeln(a[i]);
for i:=1 to 11 do begin
  write(chr(97),chr(91),i);
  write(chr(93),chr(58),chr(61));
  writeln(chr(39),a[i],chr(39),chr(59));
end;
for i:=4 to 11 do writeln(a[i]);
end.

a   [   ]   :   =   '   ;
97  91  93  58  61  39  59

Системный трюк: еще одно доказательство

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

10 LIST

Дело в том, что в бейсике есть команда LIST, которая печатает текст программы и может быть запущена изнутри программы.

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

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

Теперь рассмотрим язык программирования, в котором помимо обычных возможностей есть встроенная процедура

GetProgramText (var s: string)

Эта процедура помещает текст исходной программы в строку s. Несмотря на некоторую необычность этой идеи, вполне можно представить себе интерпретатор этого языка и интерпретация этой процедуры не представляет труда, так как интерпретатору, разумеется, доступен текст программы. Сделаем еще один шаг и представим себе, что в этом языке есть также процедура

ExecuteProgram (s: string)

Эта процедура передает управление программе, текст которой находится в строке s, считая входом этой программы вход исходной программы (как сказал бы настоящий программист, " передавая программе s дескриптор входного потока"). И в этом случае понятно, как должен действовать интерпретатор языка: он должен рекурсивно вызвать себя на содержимом строки s и входных данных.

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

function Compute_h (x: string) : string;
begin
  ...
end;

(При этом нам даже не нужны новые возможности.) Теперь напишем программу, являющуюся неподвижной точкой функции h:

program fixed_point;
   var s: string;
   function Compute_h (x:string) : string;
   begin
     ...
   end;
begin
   GetProgramText (s);
   s := Compute_h (s);
   ExecuteProgram (s);
end.

Выполнение этой программы сразу же сводится к выполнению программы, получающейся применением к ней функции h, так что она будет неподвижной точкой по построению.

  36. Пусть h тождественная функция, то есть h(x)=x. (Тогда, разумеется, любая программа будет ее неподвижной точкой.) Какую именно программу даст нам только что описанная конструкция? (Ответ: программу, которая зацикливается на любом входе.)

Мы только что объяснили, как с помощью языка с дополнительной процедурой " получить текст программы " можно доказать теорему о неподвижной точке. Но можно рассуждать и в обратном направлении и объяснить, почему применение теоремы о неподвижной точке заменяет такую дополнительную процедуру.

В самом деле, пусть мы имеем программу p, в которой есть строка GetProgramText(s). Заменим эту строку на оператор присваивания s := t, где t некоторая строковая константа. Получится новая программа, зависящая от t. Назовем ее p(t). Согласно теореме о неподвижной точке, существует такое значение t, при котором программы t и p(t) эквивалентны. При этом t выполнение программы t эквивалентно выполнению ее текста, в котором в момент вызова процедуры GetProgramText(s) в строку s помещается текст программы t чего мы и хотели.

Теперь становится понятнее, почему теорема о неподвижной точке называется еще теоремой о рекурсии. В самом деле, рекурсия состоит в том, что мы вызываем программу изнутри ее самой. Здесь происходит даже больше: мы не только имеем право вызвать программу, но и можем получить доступ к ее тексту! Обычный вызов действительно является частным случаем доступа к тексту, так как мы можем вызвать процедуру интерпретации на этом тексте. (Конечно, при этом нужно включить в состав программы текст интерпретатора нашего языка программирования, записанный на этом языке.)

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

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

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

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

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

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

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

Теорема 28. Пусть U главная универсальная функция для класса вычислимых функций одного аргумента, а h всюду определенная вычислимая функция двух аргументов. Тогда существует всюду определенная вычислимая функция n одного аргумента, которая по любому p указывает неподвижную точку для функции hp, так что Uh(p,n(p))=Un(p), или, другими словами,

U(h(p,n(p)),x) = U (n(p),x)

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

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

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

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

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

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

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

Все сказанное почти без изменений переносится на главные нумерации перечислимых множеств (если W главное универсальное перечислимое множество, то всякая вычислимая всюду определенная функция h имеет неподвижную точку n, для которой Wn=Wh(n) ).

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

$$a \equiv b \Leftrightarrow W_{a} = W_{b}$$

применимо рассуждение из доказательства теоремы 25, поскольку любая вычислимая функция f имеет вычислимое всюду определенное $$\equiv$$ -продолжение.

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

$$V = \{ \langle p,x\rangle\mid \text{$f(p)$ определено и $\langle f(p), x\rangle \in W$}\}.$$

Легко понять, что это множество перечислимо (например, оно есть область определения вычислимой функции $$\langle p,x\rangle\hm\mapsto w(f(p),x)$$, где w вычислимая функция с областью определения W ). При этом Vp=Wf(p), если f(p) определено, и $$V_{p}=\varnothing$$, если f(p) не определено. Вспоминая, что W является главным универсальным множеством, мы находим всюду определенную функцию s, для которой Vp=Ws(p). Таким образом, Ws(p)=Wf(p) для тех p, для которых f(p) определено, что и требовалось.

  40. Пусть W главное универсальное множество (для класса всех перечислимых подмножеств натурального ряда). (а) Покажите, что найдется число x, для которого Wx={x}. (б) Покажите, что найдутся различные числа x и y, для которых Wx={y} и Wy={x}.

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

Простейшее (хотя не очень типичное) применение теоремы о неподвижной точке еще одно доказательство теоремы 21 о неразрешимости свойств вычислимых функций. В самом деле, пусть есть нетривиальное свойство \calA вычислимых функций, которое можно распознавать по номерам функций в главной нумерации U. Пусть p какой-то номер какой-то функции Up, обладающей этим свойством, а q какой-то номер какой-то функции Uq, им не обладающим. Тогда функция

$$h(x)=\left\{ \begin{aligned} q,\text{ если функция~$U_x$ обладает свойством~$\calA$,}\\ p,\text{ если функция~$U_x$ не обладает свойством~$\calA$} \end{aligned} \right.$$

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

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

Пусть U1 и U2 два множества пар натуральных чисел. Мы будем называть их вычислимо изоморфными, если можно найти вычислимую перестановку (биекцию) i : N -> N с таким свойством:

$$\langle x,y\rangle \in U_1 \Leftrightarrow \langle i(x),i(y)\rangle \in U_2.$$

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

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

$$\langle x,y\rangle \in U_1 \Leftrightarrow \langle i(x),y\rangle \in U_2.$$

Заметим, что вычислимая перестановка по второму аргументу сохраняет универсальность: если $$U \subset N^{2}$$ главное универсальное множество, а i : N -> N вычислимая перестановка, то множество пар $$\langle x,y\rangle$$, для которых $$\langle x, i(y)\rangle\hm\in U$$, также является главным универсальным множеством. Поэтому из теоремы об изоморфизме главных нумераций перечислимых множеств можно вывести такое следствие: для всякой вычислимой перестановки i найдется такая вычислимая перестановка i', что

$$\langle x,y\rangle \in U_1 \Leftrightarrow \langle i'(x), i(y)\rangle \in U_2.$$

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

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

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

Пусть U1 и U2 произвольные главные нумерации перечислимых множеств, а I : N -> N вычислимая функция. Тогда существует такая вычислимая биекция i' : N -> N, что при любом k множество с номером k в нумерации U1 I -соответствует множеству с номером i'(k) в нумерации U2.

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

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

Аналогичная теорема верна и для главных универсальных функций.

Теорема 30. Пусть F1,F2 : N -> N две главные универсальные функции для вычислимых функций одного аргумента. Тогда найдется такая вычислимая перестановка i, что

$$F_{1}(x,y)=z \Leftrightarrow F_{2}(i(x),i(y))=i(z)$$

для любых натуральных x, y и z.

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

  43. Докажите, что в любом разумном (задающем главную нумерацию) языке программирования существует последовательность различных программ p0,p1,p2, ... с таким свойством: программа pi печатает программу pi+1. (Указание: используйте предыдущую задачу.)