Содержание

Введение

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 и х. Эта функция и будет искомым $IMAGE6$-продолжением. В самом деле, если f(n) определено, то s(n) будет другим номером той же функции, что и f(n). (Отметим, что если f(n) не определено, то s(n) будет одним из номеров нигде не определённой функции.)

Для завершения доказательства теоремы о неподвижной точке осталось проверить, что указанные два свойства отношения эквивалентности несовместны. Возьмём вычислимую функцию f, от которой никакая вычислимая функция не может отличаться всюду (например, диагональную функцию х → U(x, х) для некоторой вычислимой универсальной функции U). По предположению существует всюду определённое вычислимое $IMAGE6$-продолжение g функции f. Рассмотрим функцию t(x) = h(g(x)), где h — вычислимая всюду определённая функция, не имеющая $IMAGE8$-неподвижной точки. Тогда t будет всюду отличаться от f. В самом деле, если f(x) определено, то f(x) $IMAGE9$ g(х) $IMAGE10$ h(g(x)) = t(x), и потому f(x) $IMAGE11$ t(x). Если же f(x) не определено, то этот факт сам по себе уже отличает f(x) и t(x).

Теорему о неподвижной точке можно переформулировать и так:

Теорема 2. Пусть U(n, x) — главная вычислимая универсальная функция для класса вычислимых функций одного аргумента. Пусть V(n, x) — произвольная вычислимая функция. Тогда функции U и V совпадают на некотором сечении: найдётся такое р, что Up = Vp, то есть U(p, n) = V(p, n) для любого n.

Так как функция U является главной, найдём такую всюду определённую вычислимую функцию h, что V(n,x) = U(h(n),x) при всех n и x. Осталось взять в качестве р неподвижную точку функции h.

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

Поучительно развернуть цепочку приведённых рассуждений и проследить, как строится неподвижная точка. Для наглядности вместо U(n,x) мы будем писать [n](x) и читать это «результат применения программы n к входу x»;

Рассуждение начинается с рассмотрения «диагональной» функции U(x,x), которую теперь можно записать как [x](x) (результат применения программы x к себе). Далее мы строим её всюду определённое -продолжение. Это делается так. Выражение [[x] (x)] (у) вычислимо зависит от двух аргументов. Мы вспоминаем, что U есть главная универсальная функция, и находим такую программу g, что [[g](x)](y) = [[x] (x)] (у) при всех x и у. При этом [g](x) определено для всех x. Пусть мы хотим найти неподвижную точку программы h. Мы рассматриваем композицию [h]([g](x)). Это выражение вычислимо зависит от x, и потому существует программа t, для которой [t](x) = [h](g(x)) при всех x. Эта программа применима ко всем x, поскольку таковы h и g. Теперь неподвижной точкой будет [g](t). Чтобы убедиться в этом, мы должны проверить, что [[g](t)](x) = [h ([g](t))] (x) для всех x. В самом деле, по свойству g имеем [[g](t)](x) = [[t](t)](x). Вспоминая определение t, это выражение можно переписать как [[h] ([g](t))] (x) — что как раз и требовалось.

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

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

10 LIST

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

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

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

можно найти и для первой нумерации (для которой мы теорему считаем доказанной).

Теперь рассмотрим язык программирования, в котором помимо обычных возможностей есть встроенная процедура

GetProgramText (var s: string)

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

ExecuteProgram(s: string)

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

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

function Compute_h (x: string) : string; begin

end;

(При этом нам даже не нужны новые возможности.) Теперь напишем программу, являющуюся неподвижной точкой функции А:

program fixed_point; var s: string;

function Compute_h (x:string) : string; begin

end; begin

GetProgramText (s);

s := Compute_h (s);

ExecuteProgram (s); end.

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

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

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

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

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

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

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

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

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

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

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

Мы видели, что неподвижная точка строится конструктивно. Поэтому если мы ищем неподвижную точку для функции h $IMAGE15$, вычислимо зависящей от параметра р, то и результат нашего построения будет вычислимо зависеть от параметра р.

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

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

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

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

В самом д