Рекурсивные функции
Все рассматриваемые здесь функции действуют из подмножества в , где - любое натуральное число.Также будем считать что натуральное число.
Примитивно рекурсивные функции
Основные определения
Рассмотрим следующие правила преобразования функций:
- Рассмотрим -местную функцию и -местных функций . Тогда после преобразования у нас появится - местная функция .
- Это правило называется правилом подстановки
- Рассмотрим -местную функцию и -местную функцию . Тогда после преобразования у нас будет -местная функция , которая определена следующим образом:
- Это правило называется правилом рекурсии,при этом будем говорить что рекурсия запускается по аргументу .
| Определение: |
| Примитивно рекурсивными называют функции, которые можно получить с помощью правил подстановки и рекурсии из константной функции , функции и набора функций где . |
Заметим, что если — -местная примитивно рекурсивная функция, то она определена на всем множестве , так как получается путем правил преобразования из всюду определенных функций, и правила преобразование не портят всюду определенность. Говоря неформальным языком, рекурсивные функции напоминают программы, у которых при любых входных данных все циклы и рекурсий завершатся за конечное время.
Благодаря проекторам мы можем делать следующие преобразования:
- В правиле подстановки можно использовать функции с разным числом аргументов. Например, подстановка эквивалентна , но если не константная функция то все подставляемые функции должны иметь хотя бы один аргумент.
- В рекурсии не обязательно вести индукцию по последнему аргументу. Следует из того что мы можем с помощью проекторов поставить требуемый аргумент на последнее место.
В дальнейшем вместо будем писать просто , подразумевая требуемое нам .
Арифметические операции на примитивно рекурсивных функциях
n -местный ноль
- функция нуля аргументов.
Выразим сначала
, где
Теперь выразим
, где
Константа равна
- n местная константа, получается аналогичным к образом.
Сложения
, где
Умножения
, где
Вычитания
Если , то , иначе .
Рассмотрим сначала вычитания единицы
, где
Теперь рассмотрим
, где
Операции сравнения
если , иначе
если , иначе если , иначе
Сначала выразим
, где
Теперь все остальные функции
IF
, где
Деление
, если . Если же , то и все связанные с делением функции равны каким то ,не интересными для нас, числами.
Сначала определим — функция равна максимальному числу меньшему и которое нацело делится на .
, где ,
или не формально если то , иначе
Теперь само деления
, где
или не формально если то , иначе
Остаток от деления выражается так:
Теорема о примитивной рекурсивности вычислимых функций
Теорема о рекурсии
| Теорема (О рекурсии): |
Пусть — вычислимая функция. Тогда найдётся такая вычислимая , что . |
| Доказательство: |
|
Приведем конструктивное доказательство теоремы.
Пусть есть вычислимая . Будем поэтапно строить функцию .
p(y){
V(x,y) {...}
main() {
return V(getSrc(), y)
}
string getSrc() {...}
}
Теперь нужно определить функцию . Предположим, что внутри мы можем определить функцию , состоящую из одного оператора , которая вернет весь предшествующий ей код. Тогда перепишется так.
p(y){
V(x,y) {...}
main() {
return V(getSrc(), y)
}
string getSrc() {
string src = getOtherSrc();
return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
}
string getOtherSrc() {...}
}
Теперь определяется очевидным образом, и мы получаем итоговую версию функции
p(y){
V(x,y) {...}
main() {
return V(getSrc(), y)
}
string getSrc() {
string src = getOtherSrc();
return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
}
string getOtherSrc() {
return " p(y){ // Возвращаем весь предыдущий код
V(x,y) {...}
main() {
return V(getSrc(), y)
}
string getSrc() {
string src = getOtherSrc();
return src + "string getOtherSrc() {" + "\n" + "return" + src + "\n" + "}";
}";
}
}
|
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
Приведем так же альтернативую формулировку теоремы и альтернативное (неконструктивное) доказательство.
| Теорема (о неподвижной точке, Клини): | ||||||
Пусть — универсальная функция, — всюду определённая вычислимая функция. Тогда найдется такое , что .
Другими словами: нельзя найти алгоритма, преобразующего про- граммы, который бы по каждой программе давал другую (не эквива- лентную ей). | ||||||
| Доказательство: | ||||||
|
Начнём с доказательства леммы.
Теперь определим отношение так: . Покажем, что для него выполнено первое утверждение леммы. | ||||||
