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

а [ ] : = ' ;

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