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

, теж ПРФ.

Тeорeма 6.3. Нехай (n+1)-арна функцiя g та n-арнi функцiї ( i ( \xF02D ПРФ. Тодi n-арна функцiя h, задана умовою

\xF02D теж ПРФ.

Теореми 6.6.1-6.6.3 називають теоремами сумування. Замiнивши в цих теоремах символ суми ( на символ добутку (, одержимо теореми мультиплiкацiї.

Кажуть, що (п+1)-арна функцiя f отримується iз (n+1)-арної функцiї g за допомогою операцiї обмеженої мiнiмiзацiї, якщо вона задається таким спiввiдношенням:



((g(x1, ..., xn, z)=0).

Тeорeма 6.4 (про обмeжeну мiнiмiзацiю). Нехай (n+1)-арна функцiя g є ПРФ. Тодi (n+1)-арна функцiя f, задана умовою

((g(x1, ..., xn, z)=0) \xF02D теж ПРФ .

((g(x1,..., xn, у)=0) теж є ПРФ .

), звідки [x1/x2] є ПРФ за теоремою 6.6.3.

([x1/x2]).

Зауважимо, що беручи тут довизначену функцію [x1/x2], дістане-мо довизначену функцію mod(x1, x2): mod(x1,0)=0. Така довизначена функція mod(x1, x2) є ПРФ.

] є ПРФ.

] є ПРФ.

.



Приклад 18. Функцiя р(x) \xF02D х-ве просте число, \xF02D є ПРФ (тут р(0)=2, р(1)=3, р(2)=5 і т.д.)

.

Приклад 19. Функцiя ex(x, y) \xF02D степінь числа р(x) в числі у, \xF02D є ПРФ при довизначенні ех(x, 0)=0.

Справдi, ex(x, y)=(z(y(nsg(mod(y, p(x)z+1))(sg(y)=0).

7. ПРОГРАМОВАНI ФУНКЦIЇ НА N

Програмна алгебра (P, K) задається парою (B, K), де множина функцій P \xF02D основа алгебри, K \xF02D множина композицiй (операцiй) над функцiями із P, B (P\xF020\xF02D множина базових функцiй [22]. Примiтивні програмні алгебри (ППА) - це програмнi алгебри функцiй з простими типами даних. До таких функцiй належать, зокрема, квазиарні, Х-арні та п-арні функцiї, завданi на неструктурованих множинах (напри-клад, на множині N, на множинi R). Kомпозицiями ППА є операцiї суперпозицiї, циклу та розгалуження.

.

Кожну V-квазиарну функцiю на N можна трактувати як предикат, інтерпретуючи значення 0 як істиннісне значення “F”, а довільне значення а(0 \xF02D як істинісне значення “Т”. Тому для випадку V-квазиарних функцiй на N дамо наступні визначення операцій розгалуження та циклу.

Операцiя розгалуження N( V-квазиарним функцiям g, h та ( ставить у вiдповiднiсть V-квазиарну функцiю f, значення f(d) якої для кожного d(VA визначається так:



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

, розгалуження N( та циклу N\x263Cv .