Содержание

Введение

1.  Теорема о неподвижной точке

2.1 Неподвижная точка и отношения эквивалентности

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

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

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

Заключение

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

Введение

Рекурсивные функции (от позднелатинского recursio - возвращение), название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами. Рекурсивные функции были введены в 30-х гг. 20 в. С.К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя, Ж. Эрбрана и др. математиков.

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

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

1. ТЕОРЕМА О НЕПОДВИЖНОЙ ТОЧКЕ

1.1 Неподвижная точка и отношения эквивалентности

Теорема 1. Пусть U — главная вычислимая универсальная функция для класса вычислимых функций одного аргумента, a h — произвольная всюду определённая вычислимая функция одного аргумента. Тогда существует такое число n, что Un = Uh(n), то есть n и h(n) — номера одной функции.

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

Рассмотрим произвольное отношение эквивалентности (которое мы будем обозначать x  у) на множестве натуральных чисел. Мы покажем, что следующие два свойства этого отношения не могут выполняться одновременно:

Для всякой вычислимой функции f существует всюду определённая вычислимая функция g, являющаяся её -продолжением (это означает, что если f(x) определено при некотором x, то g(х)  f(x)).

Существует всюду определённая вычислимая функция h, не имеющая -неподвижной точки.

Если x  у — отношение равенства (x = у), то второе свойство выполнено (положим, например, h(n) = n + 1), поэтому не выполнено первое. Теорема о неподвижной точке получится, если x = у понимать как Ux = Uy (x и y — номера одной и той же функции). В этом случае выполнено первое свойство, как мы сейчас убедимся, и потому не выполнено второе.

Почему выполнено первое свойство? Пусть f — произвольная вычислимая функция одного аргумента. Рассмотрим функцию V(n, x) = U(f(n), x). Поскольку U является главной универсальной функцией, найдётся всюду определённая функция s, для которой V(n, x) = U(s(n),x) при всех n и х. ............