ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Обчислюваність квазіарних функцій на N. Квазіарні ЧРФ. Алгебри КЧРФ та фінарних ЧРФ. Операторні терми (ОТ).

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

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

S (f, g1,..., gn)(d) = f(d [v1ag1(d),...,vnagn(d)]).

Операц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 , Ry,z та My , назвемо V-квазиарною частково рекурсивною функцiєю (скорочено V-КЧРФ).

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

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

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 ), носiєм Âq якої є клас всiх V-КЧРФ, а операцiями - операцiї S , Ry,z та My , назвемо алгеброю V-КЧРФ.

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

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

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

2) якщо t0, t1, ..., tn - ОТ, то S (t0, t1, ..., tn) - ОТ;

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ю о.

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти