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

P ={X#Y#R(X|#Y|#R|,

X##R(X|##,

#Y#R(#Y|# }.

5. ОБЧИСЛЮВАНІСТЬ КВАЗИАРНИХ ФУНКЦІЙ НА N

, примiтивної рекурсiї Ry,z та мiнiмiзацiї My .

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

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

\xF02D\xF020при у(іт(d) значення f(d) невизначене;

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

f(d(у(0) = g(d(у(0(z(0);

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

f(d(у(0) = g(d(у(0(z(0);

f(d(у(1) = h(d(у(0(z(f(d(у(0))

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

f(d) = f(d(у(b) = h(d(у(b-1(z(f(d(у(b-1)).

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

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

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

\xF02D\xF020значення g(d(у(0) невизначене;

\xF02D\xF020для кожного k(N значення g(d(у(k) визначене та (0;

\xF02D\xF020для всiх k<а значення g(d(у(k) визначене та (0, а значення g(d(у(a) невизначене.

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

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





, Ry,z та My , назвемо V-квазиарною частково рекурсивною функцiєю (скорочено V-КЧРФ).

, Ry,z та My , назвемо V-фінарною частково рекурсивною функцiєю (скорочено V-ФЧРФ).

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

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