Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій, Детальна інформація

4. Кожна ПРФ - тотальна алгоритмiчно обчислювана функцiя.

5. Кожна ЧРФ - алгоритмiчно обчислювана функцiя.

6. Кожна РФ - тотальна алгоритмiчно обчислювана функцiя.

7. Для відповідних класів функцій мають місце спiввiдношення ПРФ(РФ(ЧРФ.

Алгебра ((; R, M, S1, S2, ...), носiєм ( якої є клас всiх ЧРФ, а операцiями – операцiї R, M та Sn+1, де n(1, називається алгеброю ЧРФ, або алгеброю Чoрча.

Алгебра ((; R, S1, S2, ...), носiєм ( якої є клас всiх ПРФ, а операцiями \xF02D операцiї R та Sn+1, де n(1, називається алгеброю ПРФ.

, де n(m(1, символiв операцiй R, M та Sn+1, де n(1, а також допомiжних символiв (, ) та , .

Дамо iндуктивне визначення ОТ алгебри ЧРФ.

1) кожен символ базової функцiї є ОТ; такі ОТ назвемо атомарними;

2) якщо t0, t1, ..., tn \xF02D\xF020ОТ, то Sn+1(t0, t1, ..., tn) \xF02D ОТ;

3) якщо t1 та t2 \xF02D ОТ, то R(t1, t2) \xF02D ОТ;

4) якщо t \xF02D\xF020ОТ, то M(t) \xF02D ОТ.

Аналогiчно дається індуктивне визначення ОТ алгебри ПРФ.

) не мають значення.

Зауважимо, що завдання ЧРФ операторними термами не є однозначним. Наприклад, операторнi терми о, S2(о, s), S2(о, о) та S3(о, S2(о, s)) задають одну i ту ж функцiю о(x).

Розглянемо приклади ПРФ, ЧРФ та РФ.

Приклад 1. Функцiї-константи \xF02D ПРФ.

);

)...).

Приклад 2. Функцiя f(x1, x2)=x1+x2 \xF02D ПРФ. Справдi, маємо

(x1);

f(x1, x2+1) = x1+(x2+1) = (x1+x2)+1 = s(x1+x2) = s(f(x1, x2)).

)(x1, x2, x3).

)).

Приклад 3. Функцiя f(x1, x2)=x1(x2 \xF02D ПРФ. Справдi, маємо

f(x1, 0) = 0 = о(x1);

f(x1, x2+1) = x1((x2+1) = x1(x2+x1 = f(x1, x2)+х1.

)), де ( \xF02D операторний терм функцiї x1+x2 .

\xF02D ПРФ. Справдi, маємо

f(x1, 0) = (x1)0 = 1;