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

Каждый алгоритм задает функцию, поскольку по набору исходных данных выдает

Совокупность тех элементов множества X, у которых есть соответствующие элементы в

Если область определения функции из X в Y совпадает с множеством

Функция у (x1, х2, ..., хn) называется вычислимой, если существует

Идея построения точного определения алгоритма, опирающегося на понятие вычислимой функции,

Какие функции могут быть вычислимыми?
Как описать такие алгоритмически

В теории РФ принят конструктивный подход:
все множество исследуемых объектов

Все вычислимые функции можно построить на основе трех элементарных функций

1) Тождественное равенство нулю:
On (x1, x2,…, xn)= 0
n-местная функция

2) Функция следования
S1(x) = x+1
Одноместная функция, сопоставляющая любому

3) Функция тождественного повтора одного из аргументов (функция проекции):
n-местная функция,

Пример1 Вычисление простейших функций

2.2. Операторы

1) Оператор суперпозиции (подстановки)

Оператором суперпозиции называется подстановка в функцию от

Говорят, что функция h получена из функций g, f1,..., fn

Пример 2

Найти значение S(S1, O1)
g(x) = S1, f (x)= O1 ->

Пример 3

Найти значение S (I22, I11 ,О1)
В этом случае конечная функция

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

Оператор примитивной рекурсии определяет (n+1)-местную функцию f

Независимо от числа переменных в f рекурсия ведется только по

Если умеем находить значения функций g и h, то

Пример 4.

Пусть g(x) = x – функция от 1 переменной (n=1),

f (x, 0) = g(x) = x
f (x, 1) = h

Если нужно доказать примитивную рекурсивность некоторой функции, нужно ее представить

Частичная функция f (х1,х2,…,хn) называется примитивно рекурсивной, если ее можно получить

Пример 5. Покажем, что функция константа является примитивно-рекурсивной
f(x) = m =

Пример 6. Покажем, что двухместная функция f(х,у) = х + у

f сум (x,0) = g(x) = x,
f сум (x, 1) =

Пример 7. Покажем, что двухместная функция f(х,у) = х*у является примитивно-рекурсивной
Для

Определим функции g и h
При у=0 fумн(x, 0) = x*0=

fумн(x,0) = g(x) = 0,
fумн(x,1) = h(x,0, fумн(x,0)) = x+ fумн(x,0)

Функция f(x,y)=х*у образуется из простейшей функции тождественного равенства нулю и

Так как функция f является функцией 2х аргументов, то для

f ст (x,0) = g(x) = 1,
f ст (x,1) = h(x,0,

Таким образом, из простейших функций с помощью операторов суперпозиции и

Однако, не все вычислимые функции можно описать как примитивно-рекурсивные (пример

Функция f(х1,х2,…,хn) называется частично рекурсивной, если ее можно получить с помощью

3) μ-оператор (оператор минимизации для функции n аргументов)

Пусть задана функция f(х1,х2,…,хn-1,

Оператор минимизации “следит”, при каком значении выбранного аргумента наблюдаемая им

Работа μ-оператора

Рассмотрим F(х1,х2,…,хn-1) = μy[f(х1,х2,…,хn-1,y) = 0],
где y -

Для вычисления функции F:
Вычисляем f(х1,х2,…,хn,0); если значение равно нулю, то полагаем

Пример 8. работа μ-оператора

Пусть функция g(х, y) = х -

Доказано, что:
множество частично-рекурсивных функций совпадает с множеством вычислимых функций

Рассмотрим как выполняются основные требования к алгоритмам для алгоритмической модели

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

Результатом является значение частично-рекурсивной функции, вычисляемой в процессе применения операторов

Таким образом, понятие ЧРФ является исчерпывающей формализацией понятия алгоритма.
Это

Вопросы к лекции

1. Как понятие алгоритма связано с понятием вычислимой функции?
2. Перечислите

Семинар

Задание 1. Применение оператора суперпозиции

Даны 3 функции от двух переменных:
f1(x1, x2)

Задание 2 (самостоятельно)

Даны три одноместные функции:
f1(x) = O1(x)
f2(x) = O1(x)
f3(x) =

Задание 3 Применение оператора примитивной рекурсии

Пусть
g(x) = 0 – функция

Задание 4 (самостоятельно)

Пусть
g(x1,x2) = x1*x2 – функция от 2 аргументов