5.2. Программа, печатающая свой текст

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

р и-)- (программа, которая на любом входе печатает р)

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

Формально говоря, это следствие можно выразить так:

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

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

Ясно, что это рассуждение применимо для любого языка программирования; то, что мы упомянули язык паскаль, роли не играет.

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

напечатать два раза, второй раз в кавычках, такой текст; «напечатать два раза, второй раз в кавычках, такой текст;»

Чтобы написать что-то похожее на паскале, пона­добятся некоторые дополнительные хитрости, но идея ясна: строковая константа используется два раза. Вот один из возможных вариантов:

program selfprint;

var a:array[1..100]of string;i:integer; begin

a[l]:='program selfprint;';

a[2]:=' var a:array[l..100]of string;i:integer;'; a[3]:='begin';

a[4]:='for i:=l to 3 do writeln(a[i]);';

a[5]:='for i:=l 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[ll]:='end.';

for i:=l to 3 do writeln(a[i]); for i:=l 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.

Читая эту программу, полезно иметь в виду соответ­ствие между символами и их кодами:

а      С     ]      :      =      ' ;

97   91   93   58   61   39 59

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

БО

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

[гл. Б]

Сделав ещё один шаг, можно получить и доказатель­ство теоремы о неподвижной точке. Пусть h — некоторое преобразование паскаль-программ, у которого мы хотим найти неподвижную точку. Тогда напишем программу наподобие только что приведённой, которая будет запи­сывать свой текст в строку р, затем применять h к р, получая некоторую другую строку q, а затем запускать интерпретатор Паскаля на строке q (используя в каче­стве входа программы q вход исходной программы). Ко­нечно, эта программа уже не будет такой короткой, так как будет включать в себя (и даже два раза — первый раз просто так, а второй раз в кавычках) интерпретатор паскаля, написанный на паскале.

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

На самом деле это доказательство в сущности повто­ряет предыдущее, только в более программистских тер­минах.