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

, sz))), sz), о).

Приклад 7. Операцiю розгалуження N( можна промоделювати, використовуючи базові функції ППА-EQ-N і операції суперпозицiї та циклу. Справдi, нехай f =N(((, g, h). Тодi f=g(sg(()+h(nsg(().

.

Приклад 8. Функції min(x, y) та max(x, y) програмовані.

, ‘х, ‘у). Такі терми відповідно позначатимемо mіпxy та mахxy .

Приклад 9. Функція mod(x, y) програмована.

). Такий терм позначимо modxy .

програмована.

, sх, Su,v((uv, sy, sy), sy), 0).

Приклад 11. Функція [x, y] програмована.

, sх, Su((uy, sz), sz), 0).

Приклад 12. Функція HCK(x, y) програмована.

Справді, функцію HCK(x, y) можна подати операторним термом Sz(N\x263Cz(Su,v(+uv, modzx, modzy), sz), maxxy).

Приклад 13. Функція HCD(x, y) програмована.

, 1), minxy).

Для випадку п-арних функцій N операцiї суперпозицiї, циклу та розгалуження уточнимо наступним чином..

Операцiя N\x263C n-арним функціям g та ( ставить у вiдповiднiсть n-арну функцiю f, значення f(x1, ..., xn) якої для кожного набору значень x1, ..., xn визначається як перший елемент аm послiдовностi a0=x1, a1=f(a0, x2, ..., xn), a2=f(a1, x2, ..., xn), ..., ak=f(ak-1, x2, ..., xn), ... такий, що ((am, x2,..., xn)=0 та для всiх k
Операцiя N( n-арним функцiям g, h та ( ставить у вiдповiднiсть n-арну функцiю f, значення f(x1, ..., xn) якої для кожного набору значень x1, ..., xn визначається так:



.

Функцiю назвемо програмованою на N, якщо її можна отримати iз вказаних вище базових функцiй за допомогою скiнченної кiлькостi застосувань операцiй суперпозицiї Sn+1, розгалуження N(, циклу N\x263C.

Із наведених визначень випливають наступні твердження:

1. Якщо функцiї (, g, h алгоритмiчно обчислюванi, то функцiя N(((, g, h) теж алгоритмiчно обчислювана.

2. Якщо функцiї ( та g алгоритмiчно обчислюванi, то функцiя N\x263C((, g) теж алгоритмiчно обчислювана.

3. Кожна програмована на N n-арна функцiя є алгоритмiчно обчислюваною.

Алгебра (Nar; N(, N\x263C, S2, S3, ... ), носiєм Nar якої є клас всiх програмованих на N n-арних функцiй, а операцiями \xF02D операцiї N(, N\x263C та Sn+1, де n(1, називається примiтивною програмною алгеброю програмованих на N n-арних функцiй (ППА-Ar-N).

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

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

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

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