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

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

Основними обчислюваними операцiями для п-арних функцiй на множині N є наступні операції: операція суперпозицiї Sn+1, операція примiтивної рекурсiї R, операція мiнiмiзацiї M.

Операцiя Sn+1 n-арнiй функцiї g(x1,...,xn) та n функцiям g1(x1,...,xт), ..., gn(x1,...,xm) одної i тої ж арностi ставить у вiдповiднiсть функцiю f(x1,...,xm) = g(g1(x1,...,xт), ..., gn(x1,...,xm)).

Таку функцiю позначають Sn+1 (g, g1, ..., gn), її арність співпадає з арнiстю функцiй g1, ..., gn.

Операцiя примiтивної рекурсiї R n-арнiй функцiї g та (n+2)-арнiй функцiї h ставить у вiдповiднiсть (n+1)-арну функцiю f, яку позначають R(g,h), що задається рекурсивним визначенням

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

f(x1,...,xn,y+1) = h(x1,...,xn,y, f(x1,...,xn,y))

Це означає, що для всiх значень a1,..., an, b значення f(a1,...,bn ,b) обчислюється так:

f(a1,...,an,0) = g(a1,...,an)

f(a1,...,an,1) = h(a1,...,an,0, f(a1,...,an,0))

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

f(a1,...,an ,b) = h(a1,...,an ,b-1, f(a1,...,an ,b-1))

При n=0 вважаємо, що функцiя g \xF02D 1-арна константа.

Операцiя мiнiмiзацiї M кожній (n+1)-арнiй функцiї g ставить у вiдповiднiсть n-арну функцiю f, яку позначають M(g), що задається спiввiдношенням

f(x1,...,xn) = (y(g(x1,...,xn,y)=0)

Це означає, що для всiх значень x1, ..., xn значення функцiї f(x1,...,xn) обчислюється так. Послiдовно обчислюємо значення g(x1,...,xn,y) для y=0, 1, 2, ... Перше таке значення y, що g(x1,...,xn,y)=0, буде шуканим значенням f(x1,...,xn). При цьому для всiх t
Із визначення випливає, що процес обчислення значення (y(g(x1,...,xn,y)=0) нiколи не закiнчиться в таких випадках:

\xF02D\xF020значення g(x1,...,xn,0) невизначене;

\xF02D\xF020для всiх значень у значення g(x1,...,xn,y) визначене та (0;

\xF02D\xF020для всiх t
Зрозуміло, що функцiя g може бути тотальною, а функцiя f=M(g) \xF02D навiть всюди невизначеною. Наприклад, f(x)=(y(x+y+1=0).

(x1,...,xn)=xm , де n(m(1.

Всi базовi функцiї тотальнi та алгоритмiчно обчислюванi.

Функцiю, яку можна отримати iз базових функцiй за допомогою скiнченної кiлькостi застосувань операцiй суперпозицiї та примiтивної рекурсiї, називають примiтивно рекурсивною функцiєю (скорочено ПРФ).

Функцiю, яку можна отримати iз базових функцiй за допомогою скiнченної кiлькостi застосувань операцiй суперпозицiї, примiтивної рекурсiї та мiнiмiзацiї, називають частково рекурсивною функцiєю (скорочено ЧРФ).

Тотальну ЧРФ називають рекурсивною функцiєю (скорочено РФ).

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

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

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

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