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

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

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

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

V = {(р,х) / f(р) определено и (f(р), x) W}.

Легко понять, что это множество перечислимо (например, оно есть область определения вычислимой функции (р, x) → w(f(р),x), где w — вычислимая функция с областью определения W). При этом ), если f(р) определено, и , если f(р) не определено. Вспоминая, что W является главным универсальным множеством, мы находим всюду определённую функцию s, для которой . Таким образом, ) для тех р, для которых f(р) определено, что и требовалось.

3. Практическая часть

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

р → (программа, которая на любом входе печатает р) не имело бы неподвижной точки.

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

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

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

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

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

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

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;