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

Содержание

Введение

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 и х. Эта функция и будет искомым

-продолжением. В самом деле, если f(n) определено, то s(n) будет другим номером той же функции, что и f(n). (Отметим, что если f(n) не определено, то s(n) будет одним из номеров нигде не определённой функции.)

Для завершения доказательства теоремы о неподвижной точке осталось проверить, что указанные два свойства отношения эквивалентности несовместны. Возьмём вычислимую функцию f, от которой никакая вычислимая функция не может отличаться всюду (например, диагональную функцию х → U(x, х) для некоторой вычислимой универсальной функции U). По предположению существует всюду определённое вычислимое

-продолжение g функции f. Рассмотрим функцию t(x) = h(g(x)), где h — вычислимая всюду определённая функция, не имеющая -неподвижной точки. Тогда t будет всюду отличаться от f. В самом деле, если f(x) определено, то f(x) g(х) h(g(x)) = t(x), и потому f(x) 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.

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