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

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

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

 

 

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

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

 

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

 

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

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

 

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

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

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

Теорема 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;

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 на её тексте, после чего это значение воспринимается как программа и применяется к входу.

клини неподвижный точка программирование

Заключение

 

В курсовой работе были рассмотрены следующие вопросы:

· Дана теорема о неподвижной точке и её доказательство.

· Рассмотрен способ доказательства теоремы с помощью языка с дополнительной процедурой «получить текст программы»

· Приведён классический пример применения теоремы о неподвижной точке.

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

 

Список литературы

 

1. Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть3. Вычислимые функции. Москва, 1999 МЦНМО.

2. Х. Роджерс. Теория вычислимых функций и эффективная вычислимость. Издательство «МИР» Москва, 1972г.

3. http://wikipedia.ru