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

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

10 LIST

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

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

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

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

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

GetProgramText (var s: string)

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

ExecuteProgram(s: string)

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

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

function Compute_h (х: 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) = х. (Тогда, разумеется, любая программа будет её неподвижной точкой.) Какую именно программу даст нам только что опи­санная конструкция? (Ответ: программу, которая зациклива­ется на любом входе.)

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

В самом деле, пусть мы имеем программу р, в которой есть строка GetProgramText(s). Заменим эту строку наоператор присваивания э := I, где t — некоторая стро­ковая константа. Получится новая программа, зависящая от /. Назовём её р(/). Согласно теореме о неподвижной точке, существует такое значение /, при котором про­граммы / ж р({) эквивалентны. При этом t выполнение программы / эквивалентно выполнению её текста, в ко­тором в момент вызова процедуры Се1Ргс^гатТех1;(з) в строку э помещается текст программы / — чего мы и хотели.

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