Основними обчислюваними операцiями для випадку еквітонних V-квазиарних функцій на множині N є параметричні операцiї суперпозицiї S , примiтивної рекурсiїR_y_,_z та мiнiмiзацiї M_y .

(n+1)-арна композиція суперпозиції S з параметрами v₁,...,v_nÎV кожним V-квазіарним функціям f, g₁, ..., g_n ставить у відповідність V-квазіарну функцію, яку позначимо S (f, g₁,...,g_n), значення якої для кожного dÎ^VА обчислюється так:

S (f, g₁,..., g_n)(d) = f(d [v₁ag₁(d),...,v_nag_n(d)]).

Операцiя примiтивної рекурсiї R_y_,_z з параметрами у, z двом V-квазиарним функцiям g та h ставить у вiдповiднiсть V-квазиарну функцiю f, яку позначають R_y_,_z (g, h).

Для кожного dÎ^VN значення f(d) визначається таким чином:

- при уÏіт(d) значення f(d) невизначене;

- при уÎіт(d) значення f(d) визначається рекурсивною схемою

f(dÑуa0) = g(dÑуa0Ñza0);

f(dÑуaа+1) = h(dÑуaаÑzaf(dÑуaа)) для всіх a<d(y).

Це означає, що для всiх dÎ^VN таких, що уÎіт(d) та d(y)=b, значення f(d) обчислюється так:

f(dÑуa0) = g(dÑуa0Ñza0);

f(dÑуa1) = h(dÑуa0Ñzaf(dÑуa0))

... ... ... ... ... ... ... ... ... ... ...

f(d) = f(dÑуab) = h(dÑуab-1Ñzaf(dÑуab-1)).

Операцiя мiнiмiзацiї M_y з параметром у V-квазиарній функцiї g ставить у вiдповiднiсть V-квазиарну функцiю f, яку позначають M_y(g). Для кожного dÎ^VN значення f(d) визначається як перше аÎN таке, що g(dÑуaa)=0 і для всiх k<а значення g(dÑуak) визначене та ¹0. Якщо таке aÎN не iснує, то f(d).

Це означає, що кожного dÎ^VN значення f(d) обчислюється так. Послiдовно обчислюємо значення g(dÑуak) для k=0, 1, 2, ... Перше таке аÎN, що g(dÑуaa)=0, буде шуканим значенням f(d). При цьому для всiх k<а значення g(dÑуak) визначені та ¹0.

Процес обчислення значення M_y(g)(d) нiколи не закiнчиться в таких випадках:

- значення g(dÑуa0) невизначене;

- для кожного kÎN значення g(dÑуak) визначене та ¹0;

- для всiх k<а значення g(dÑуak) визначене та ¹0, а значення g(dÑуaa) невизначене.

Базовими функцiями для випадку V-квазиарних функцiй, заданих на множинi N, вважатимемо функцiї о, s_х та функцiї розіменування ‘v. Вказані функції визначаються так:

о(d)=0 для всіх dÎ^VN ;

‘v(d)=d(v)=

s_х(d)= d(х)+1 =

Функцiю, яку можна отримати iз базових функцiй о, s_х‘v за допомогою скiнченної кiлькостi застосувань операцiй S , R_y_,_z та M_y , назвемо V-квазиарною частково рекурсивною функцiєю (скорочено V-КЧРФ).

Функцiю, яку можна отримати iз фінарних функцiй о, s_х‘v за допомогою скiнченної кiлькостi застосувань операцiй S , R_y_,_z та M_y , назвемо V-фінарною частково рекурсивною функцiєю (скорочено V-ФЧРФ).

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

1. Функцiя R_y_,_z (g, h) алгоритмiчно обчислювана відносно функцій g, h та відносно скінченноіменних операцій врізки на ^VN і відносно V-ІМ над N як функцій .

2. Функцiя R_y_,_z (g, h) алгоритмiчно обчислювана відносно V-фінарних функцій g та h.

3. Функцiя М_y(g) алгоритмiчно обчислювана відносно функції g та відносно скінченноіменних операцій врізки на ^VN і відносно V-ІМ над N як функцій .

4.Функцiя М_y(g) алгоритмiчно обчислювана відносно V-фінарної функції g.

5. Операції R_y_,_z та M_y зберігають еквітонність V-квазиарних функцій, завданих на множинi N.

6. Кожна V-КЧРФ алгоритмiчно обчислювана відносно скінченно-іменних операцій врізки на ^VN та відносно V-ІМ над N як функцій.

7. Кожна V-ФЧРФ алгоритмiчно обчислювана.

8. Кожна V-КЧРФ еквітонна.

Алгебру (Âq; R_y_,_z , M_y , S ), носiєм Âq якої є клас всiх V-КЧРФ, а операцiями - операцiї S , R_y_,_z та M_y , назвемо алгеброю V-КЧРФ.

Алгебру (Âf ; R_y_,_z , M_y , S ), носiєм Âf якої є клас всiх V-ФЧРФ, а операцiями - операцiї S , R_y_,_z та M_y , назвемо алгеброю V-ФЧРФ.

Введемо поняття операторного терма (скорочено ОТ) алгебри V-КЧРФ. Алфавiт складатиметься iз символiв базових функцiй о, s_х та ‘v, символiв операцiй R_y_,_zM_y та S , а також допомiжних символiв (, ) та , . Дамо iндуктивне визначення ОТ алгебри V-КЧРФ:

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

2) якщо t₀, t₁, ..., t_n - ОТ, то S (t₀, t₁, ..., t_n) - ОТ;

3) якщо t₀ та t₁ - ОТ, то R_y_,_z (t₀, t₁) - ОТ;

4) якщо t - ОТ, то M_y (t) - ОТ.

Інтерпретуючи символи на множині Âq природним чином, маємо: кожна V-КЧРФ є значенням деякого ОТ алгебри V-КЧРФ.

При інтерпретації символів на множині Âf дістаємо, що кожна V-ФЧРФ є значенням деякого ОТ алгебри V-КЧРФ.

Якщо функцiя f є значенням ОТ t, то кажуть, що t - операторний терм функцiї f, або що f задана операторним термом t.

Зауважимо, що завдання V-КЧРФ та V-ФЧРФ операторними термами не є однозначним. Наприклад, операторнi терми о, S^х(о, s_х), S^х(о, о) та S^х,у(о, о, s) задають одну i ту ж функцiю о.

123