Содержание
Введение
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 — всюду определённая вычислимая функция, у которой мыхотим найти неподвижную точку. Запишем вычисляющий её алгоритм в виде процедурынашего языка:
functionCompute_h (x: string): string; begin
end;
(При этом нам даже не нужныновые возможности.) Теперь напишем программу, являющуюся неподвижной точкойфункции А:
programfixed_point; var s: string;
functionCompute_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/>= 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 будет главной универсальной функцией. Поэтому к ней можноприменить сформулированное только что утверждение; получим программу р, котораяпри любом входе на выходе даёт р.
Ясно, что это рассуждениеприменимо для любого языка программирования; то, что мы упомянули язык паскаль,роли не играет.
Выпишем явно программу напаскале, печатающую свой текст. (Это — хорошая задача для любителейпрограммирования.) Для начала напишем неформальную инструкцию на русском языке:напечатать два раза, второй раз в кавычках, такой текст: «напечатать два раза,второй раз в кавычках, такой текст:»
Чтобы написать что-топохожее на паскале, понадобятся некоторые дополнительные хитрости, но идеяясна: строковая константа используется два раза. Вот один из возможных вариантов:
programselfprint;
vara:array[1..100]of string;i:integer; begin
a[1]:=’program selfprint ;';
a[2]:=’ var a:array[1..100]ofstring;i:integer;’;
a[3]:=’begin’;
a[4]:=’fori:=1 to 3 do writeln(a[i]);’;
a[5]:=’ ’fori:=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]:='fori:=4 to 11 do writeln(a[i]);';
a[11]:='end.';
for i:=1 to 3do 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 11do 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. wikipedia.ru