Рекурсивные функции

Март 2, 2021

Главная
Информатика
Рекурсивные функции

Содержание

2. Эта модель рассматривает алгоритм как способ формирования одних вычислимых функций из других, т.е. одни функции конструктивно
3. Оператор суперпозиции
4. Примеры
5. Оператор примитивной рекурсии
6. Оператор примитивной рекурсии
7. Функция называется примитивно – рекурсивной, если она является элементарной или может быть получена из элементарных функций
8. Функция – константа f(x) = m s(s(s…s(Z(x))…)) m-раз 2. Сложение f(x,y)=x+y f(x,0)=x; f(x,y+1)=x+(y+1)=(x+y)+1=f(x,y)+1 Доказательство: f(x,0)=g(x)=x=I(x); f(x,y+1)
9. 3. Умножение f(x,y)=x*y f(x,0)=x*0=0; f(x,y+1)=x*(y+1)=x*y+x=f(x,y)+x Доказательство: f(x,0)=g(x)=0=Z(x); f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) =x+z= I31 (x,y,f(x,y))+I33 (x,y,f(x,y))
11. Операции конечного суммирования и конечного произведения
12. Оператор минимизации
13. Использование оператора минимизации Используя минимизацию можно получать частично –определенные функции из всюду определенных функций. Пример 2.
15. Тезис Черча Функция называется частично-рекурсивной (вычислимой по Черчу), если она может быть получена из простейших функций
17. Скачать презентацию

Слайд 2

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

других, т.е. одни функции конструктивно определяются из других.

Все элементарные функции - всюду определенные и алгоритмически вычислимые.

Эта модель рассматривает алгоритм как способ формирования одних вычислимых функций

Слайд 7

Функция называется примитивно – рекурсивной, если она является элементарной или может

быть получена из элементарных функций с помощью конечного числа применений операторов тождества, суперпозиции и примитивной рекурсии.
Если некоторые функции являются примитивно-рекурсивными, то в результате применения к ним операторов суперпозиции или примитивной рекурсии можно получить новые примитивно-рекурсивные функции.
Существует три возможности доказательства того, что функция является примитивно-рекурсивной:
а) показать, что заданная функция является простейшей;
б) показать, что заданная функция построена с помощью оператора суперпозиции;
в) показать, что заданная функция построена с помощью оператора примитивной рекурсии.

Оператор примитивной рекурсии

Функция называется примитивно – рекурсивной, если она является элементарной или

Слайд 8

Функция – константа
f(x) = m s(s(s…s(Z(x))…)) m-раз
2. Сложение
f(x,y)=x+y
f(x,0)=x;
f(x,y+1)=x+(y+1)=(x+y)+1=f(x,y)+1
Доказательство:
f(x,0)=g(x)=x=I(x);
f(x,y+1) = h(x,y,z) =

h(x,y,f(x,y)) = s(I33 (x,y,f(x,y)))
+2 =R(I11,[s1;I33]).

Примеры доказательства вычислимости функций

Функция – константа f(x) = m s(s(s…s(Z(x))…)) m-раз 2. Сложение

Слайд 9

3. Умножение
f(x,y)=x*y
f(x,0)=x*0=0;
f(x,y+1)=x*(y+1)=x*y+x=f(x,y)+x
Доказательство:
f(x,0)=g(x)=0=Z(x);
f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) =x+z= I31 (x,y,f(x,y))+I33 (x,y,f(x,y))
x2

=R(Z,[+;I33,I13])
4. Симметрическая разность (абсолютная величина разности)
Одноместная функция усеченного вычитания единицы определяется рекурсивно:

Слайд 10

Слайд 11

Операции конечного суммирования и конечного произведения

Слайд 12

Оператор минимизации

Слайд 13

Использование оператора минимизации

Используя минимизацию можно получать частично –определенные функции из всюду

определенных функций.

Пример 2. Пусть g(x) = [x/2]. Найдем функцию f(x), которая получается в результате применения оператора минимизации к этой всюду определенной функции. При каждом конкретном x значение f(x) равно минимальному корню уравнения [y/2] = x. Это уравнение имеет два корня: 2x и 2x+1. Поэтому f(x)=2x.

Использование оператора минимизации Используя минимизацию можно получать частично –определенные функции

Слайд 14

Слайд 15

Тезис Черча

Функция называется частично-рекурсивной (вычислимой по Черчу), если она может быть

получена из простейших функций с помощью конечного числа операторов суперпозиции, примитивной рекурсии и минимизации.
Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями.
Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз. Таким образом, мы не просто задаем функцию, но и точно знаем, как её вычислять.
Очевидно, каждая примитивно рекурсивная функция является частично
рекурсивной, но обратное неверно.
Введем обозначения:
KПРФ – класс примитивно рекурсивных функций;
KОРФ – класс общерекурсивных функций;
KЧРФ – класс частично рекурсивных функций.
Тогда между этими классами имеется соотношения:
KПРФ ⊆ KОРФ ⊆ KЧРФ.