Теория алгоритмов. Зюзысов В.М. - 18 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Теорема 6. Любой рекурсивный оператор является непрерывным и монотонным.
Доказательство см., например, [11, с. 194–195].
Неформально использование слова «непрерывный» для описания свойства
оператора можно объяснить следующим образом. Можно показать, что если функция h
находится «близко» от функции f (в том смысле, что они совпадают на конечном
множестве D
θ
, где θ ⊆ f ), то для непрерывного оператора Φ функция Φ(h) расположена
«близко» от функции Φ(f).
Первая теорема о рекурсии Клини представляет собой теорему о неподвижной
точке для рекурсивных операторов, и ее зачастую называют также теоремой о
неподвижной точке (из теории рекурсии).
Теорема 7 (теорема о неподвижной точке).
1
Пусть Φ: F→F – рекурсивный
оператор. Тогда существует вычислимая функция f, которая является наименьшей
неподвижной точкой для Φ, т.е
1) Φ(f) = f,
2) если Φ(h) = h, то f ⊆ h.
Отсюда если функция f всюду определена, то она является единственной неподвижной
точкой Φ.
Доказательство см., например, [11, с. 203–204].
Теорема
вызывает недоумение: пусть оператор Φ задан так: функция f(x)
отображается в функцию f(x)+1. Это отображение конечно можно задать с помощью
алгоритма (т.е. оператор рекурсивный), но разве у этого оператора есть неподвижная
точка? Да, это функция, которая нигде не определена.
Наш программисткий опыт говорит о том, что определения,
даваемые в терминах
примитивной рекурсии, имеют смысл. В случае более сложных рекурсивных определений
(см., например, функцию Аккермана) это не так очевидно – вполне можно представить
себе, что функций, удовлетворяющих тому или иному определению, вообще не
существует. Именно здесь оказывается полезной теорема 7. Рекурсивные определения
весьма общего типа могут быть представлены уравнением вида
f = Φ(f),
где Φ – некоторый рекурсивный оператор. Теорема о неподвижной точке показывает, что
такое определение имеет смысл: всегда существует даже вычислимая функция, которая
ему удовлетворяет. Поскольку в математике требуется, чтобы определения описывали
различные понятия однозначно, можно сказать, что данное рекурсивное определение
определяет наименьшую неподвижную точку оператора Φ. Таким образом, согласно
теореме 7, класс вычислимых функций замкнут относительно рекурсивного определения
очень общего типа. Таким образом, понятно, почему эту теорему называют теоремой о
рекурсии (точнее первой теоремой о рекурсии, есть также вторая теорема о рекурсии).
2.3 Куины
Куином называется программа, которая на своем выходе генерирует собственный
исходный текст. Этот термин предложил Д. Хофштадтер в честь американского философа
и математика Willard van Orman Quine (1908 – 2000).
Докажем, что куины существуют для любого универсального языка
программирования. Действительно, теорему Клини о рекурсии (или о неподвижной точке)
можно сформулировать в следующем виде: «Нельзя найти алгоритма, преобразующего
программы
, который бы по каждой программе давал бы другую (не эквивалентную ей)».
Пусть теперь дано преобразование программ:
F: p → {программа, которая на любом входе печатает p).
1
В ламбда-исчислении этой теореме соответствует утверждение о существование комбинатора
неподвижной точки.

Страницы