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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Примитивная рекурсия. При n ≥ 0 из n-местной функции f и (n+2)-местной функции
g строится (n+1)-местная функция h по следующей схеме:
h(x, 0) = f(x),
h(x, y+1) = g(x, y, h(x, y)).
•
•
•
•
При n=0 получаем (a – константа):
h(0) = a;
h(y+1) = g(y, h(y)).
Два упомянутых
способа позволяют задать только всюду определенные функции.
Частично-определенные функции порождаются с помощью третьего гёделева механизма.
Оператор минимизации. Эта операция ставит в соответствие частичной функции f:
N
k+1
→N частичную функцию h: N
k
→N, которая определяется так (x = <x
1
,..., x
k
>):
1) область определения D
h
= {x | существует x
k+1
≥0, f(x, x
k+1
) = 0 и < x, y> ∈ D
f
для всех
y ≤ x
k+1
};
2) h(x) = наименьшее значение y, при котором f(x, y) = 0.
Оператор минимизации обозначается так h(x) = µy[f(x,y) = 0].
Очевидно, что даже если f всюду определено, но нигде не обращается в 0, то µy[f(x,
y) = 0] нигде не определено. Естественный путь вычисления h(x) состоит в подсчете
значения f(x, y) последовательно для y = 0,1, 2,... до тех пор, пока не найдется y,
обращающее f(x, y) в 0. Этот алгоритм не остановится, если f(x, y) нигде не обращается в
0.
Все функции, которые можно получить из базисных функций за конечное число
шагов только с помощью трех указанных механизмов, называются
частично-
рекурсивными. Если функция получается всюду определенная, то тогда она называется
общерекурсивной. Если функция получена без механизма минимизации, то в этом случае
она называется примитивно-рекурсивной.
Любую примитивно-рекурсивную функцию можно вычислить с помощью цикла в
форме for, так как верхнюю границу для числа повторений можно указать заранее.
Оператор минимизации позволяет
описать функции, которые нельзя вычислить за заранее
ограниченное число итераций, для вычисления их значений требуется цикл в форме while.
Можно легко показать [17, с.136], что введение фиктивных переменных, а также
перестановка и отождествление переменных не выводят за пределы класса примитивно-
рекурсивных функций и класса частично-рекурсивных функций. Это проще всего
объяснить
на примерах.
Введение фиктивных переменных. Если g(x
1
, x
3
) – примитивно-рекурсивная
функция и f(x
1
, x
2
, x
3
) = g(x
1
, x
3
), то f(x
1
, x
2
, x
3
) – примитивно-рекурсивная функция.
Перестановка переменных. Если g(x
1
, x
2
) - примитивно-рекурсивная функция и
f(x
2
, x
1
) = g(x
1
, x
2
), то f есть также примитивно-рекурсивная функция.
Отождествление переменных. Если g(x
1
, x
2
, x
3
) – примитивно-рекурсивная
функция и f(x
1
, x
2
) = g(x
1
, x
2
, x
1
), то f(x
1
, x
2
) есть также примитивно-рекурсивная функция.
Примеры рекурсивности
Рассмотрим примеры частично-рекурсивных функций. Все эти примеры и много
других можно найти в [15, 17].
Сложение двух чисел
sum: <x,y> → x+y.
Эта функция является общерекурсивной в силу примитивной рекурсии
sum(x,0) = pr
1
(x) = x,
sum(x,y+1) = s(sum(x,y)) = sum(x,y)+1.
Умножение двух чисел

Страницы