Теорема о неподвижной точке (стр. 2 из 2)

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

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

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

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

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

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

= U .

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

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

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

Теорема 5. Пусть U — главная универсальная функция для класса вычислимых функций одного аргумента, а h — всюду определённая вычислимая функция двух аргументов. Тогда существует всюду определённая вычислимая функция n одного аргумента, которая по любому р указывает неподвижную точку для функции h

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

Мы видели, что неподвижная точка строится конструктивно. Поэтому если мы ищем неподвижную точку для функции h

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

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

В этой теореме мы предполагали, что семейство функций h

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

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

Всё сказанное почти без изменений переносится на главные нумерации перечислимых множеств (если 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;

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