2. Оператор рекурсии

Схема примитивной рекурсии в простейшем виде:

f ⁽ⁿ⁺¹⁾(x_1, x_{2, …,} x_n, Y₀) = q ⁽ⁿ⁾ (x_{1, …,} x_n, 0)

f ⁽ⁿ⁺¹⁾(x_1, x_{2, …,} x_n, Y_i+1) = h ⁽ⁿ⁺²⁾ (x_{1, …,} x_n, Y_i, f ⁽ⁿ⁺¹⁾( x_{1, …,} x_n, Y_i) )

Тогда оператор примитивной рекурсии может быть задан в следующем виде:

f ⁽ⁿ⁺¹⁾(x_1, x_{2, …,} x_n, Y) = R (q ⁽ⁿ⁾, h ⁽ⁿ⁺²⁾) (22)

(22) определяет операторное представление рекурсии, где h – характеризует функцию некоторого i-го шага q₀ шага рекурсии.

Пример вычисления примитивной рекурсии функции:

f(x) = x+n

q (x,0) = x

h (x, y, f(x,y))

h(x, 1, f(x,1)) = x+1

h(x, 2, f(x,2)) = x+2

7.7 Обобщенная форма операторов суперпозиции и рекурсии

Возможны два варианта представления оператора суперпозиции и рекурсии:

1. Оператор суперпозиции над простейшими вычислимыми функциями;

2. Оператор суперпозиции над функциями, вычислимость которых должна быть доказана.

f(x_1, x_{2, …,} x_n) = S¹(f¹, q ⁽ⁿ⁾_1, q ⁽ⁿ⁾_2, q ⁽ⁿ⁾_{3, …,} q ⁽ⁿ⁾_m )

f(x_1, x_{2, …,} x_n) = S² (f², q ⁽ⁿ⁾_2, q ⁽ⁿ⁾_22, q ⁽ⁿ⁾_{23, …,} q ⁽ⁿ⁾_2m)

Функция f⁽ⁿ⁾_{ki –} полученная в результате применения оператора суперпозиции простейшей вычислимой функции. Оператор суперпозиции может быть построен как реализация некоторой функции над результатами применения оператора суперпозиции к простейшим вычислимым функциям при учете других аргументов, также являющихся простейшими вычислимыми.

f(x_1, x_{2, …,} x_n) = S²(f², S¹(f¹, q ⁽ⁿ⁾_{1, …,} q ⁽ⁿ⁾_m), q ⁽ⁿ⁾_{21, …,} q ⁽ⁿ⁾_{22 …} )

В результате вложенности операторов суперпозиции может быть получен некоторый вид обобщенного оператора S.

f(x_1, x_{2, …,} x_n) = S^p (f^p,…, (S^p-i(f^p-i, S^p-(i+1)(f^p-(i+1), …., S² (f², S¹(f¹, q⁽ⁿ⁾_{11, …} , q⁽ⁿ⁾_{12, … ,} q⁽ⁿ⁾_1m) q⁽ⁿ⁾_{22 …}), …., q⁽ⁿ⁾_1,p-(i+1) , … , q⁽ⁿ⁾_m,p-(i+1)), …)….), q⁽ⁿ⁾_1p, q⁽ⁿ⁾_{2p, ….,} q⁽ⁿ⁾_mp)

7.8 Обобщенный вид оператора рекурсии

f = Sⁿ (fⁿ, R (R (R (f¹_1, f¹₂), f²_1, f²₂), f³_1, f³₂), f⁴_1, f⁴₂)

При получении функции f, являющейся результатом рекурсии, функция h’ имеет вид:

h = (R (R (R (f¹_1, f¹₂), f²_1, f²_2, f³_1, f³₂)

f = R (h(….); f⁴_1, f⁴₂)

7.9 Обобщенный вид оператора суперпозиции для множественного потока данных

Предшествующий вид оператора суперпозиции предполагал последовательное вычисление одного выражения.

Возможно вычисление совокупности выражений, результаты которых используются в обобщающем операторе суперпозиции.

Порядок:

f_1, f_{2, …. ,} f_{m, ….} f_m+n

, , ,

,

Анализ обобщенной формы оператора суперпозиции для нескольких потоков данных позволяет определить порядок реализации вычислений (определение результата функции), то есть порядок реализации функции.

Реализация распараллеливания обобщенного оператора суперпозиции для одного потока данных:

f = Sⁿ (fⁿ, … , S^k (f^k, … , S² (f², S¹ (f¹,q¹_1, q¹_{2 …} q¹_r1), q²_1, q²_{2, …,} q²_r2), … q^k_1, q^k_2, …, q^k_rk), … qⁿ_1, qⁿ_{2, … ,} qⁿ_rn)

1: f_{1 =} S (f¹, q¹_1, q¹_2, q¹_r1);

2: f_{2 =} S (f²,f_1, q²_1, …., q¹_r2)

3: f_{3 =} S (f³,f_2, q³_1, …., q¹_r3)

Последовательная форма представления оператора суперпозиции определяет некоторую конвейерную обработку, выполняемую в магистрали с n-ым количеством элементов.