![]() |
Обчислюваність квазіарних функцій на N. Квазіарні ЧРФ. Алгебри КЧРФ та фінарних ЧРФ. Операторні терми (ОТ).
Основними обчислюваними операцiями для випадку еквітонних V-квазиарних функцій на множині N є параметричні операцiї суперпозицiї S (n+1)-арна композиція суперпозиції S S Операцiя примiтивної рекурсiї Ry,z з параметрами у, z двом V-квазиарним функцiям g та h ставить у вiдповiднiсть V-квазиарну функцiю f, яку позначають Ry,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ї My з параметром у V-квазиарній функцiї g ставить у вiдповiднiсть V-квазиарну функцiю f, яку позначають My(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. Процес обчислення значення My(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 Функцiю, яку можна отримати iз фінарних функцiй о, sх‘v за допомогою скiнченної кiлькостi застосувань операцiй S Із наведених визначень випливають наступні твердження: 1. Функцiя Ry,z (g, h) алгоритмiчно обчислювана відносно функцій g, h та відносно скінченноіменних операцій врізки на VN і відносно V-ІМ над N як функцій . 2. Функцiя Ry,z (g, h) алгоритмiчно обчислювана відносно V-фінарних функцій g та h. 3. Функцiя Мy(g) алгоритмiчно обчислювана відносно функції g та відносно скінченноіменних операцій врізки на VN і відносно V-ІМ над N як функцій . 4.Функцiя Мy(g) алгоритмiчно обчислювана відносно V-фінарної функції g. 5. Операції Ry,z та My зберігають еквітонність V-квазиарних функцій, завданих на множинi N. 6. Кожна V-КЧРФ алгоритмiчно обчислювана відносно скінченно-іменних операцій врізки на VN та відносно V-ІМ над N як функцій. 7. Кожна V-ФЧРФ алгоритмiчно обчислювана. 8. Кожна V-КЧРФ еквітонна. Алгебру (Âq; Ry,z , My , S Алгебру (Âf ; Ry,z , My , S Введемо поняття операторного терма (скорочено ОТ) алгебри V-КЧРФ. Алфавiт складатиметься iз символiв базових функцiй о, sх та ‘v, символiв операцiй Ry,zMy та S 1) кожен символ базової функцiї є ОТ; такі ОТ назвемо атомарними; 2) якщо t0, t1, ..., tn - ОТ, то S 3) якщо t0 та t1 - ОТ, то Ry,z (t0, t1) - ОТ; 4) якщо t - ОТ, то My (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ю о. |
|
|