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

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

1. Функцiя N(((, g, h) алгоритмiчно обчислювана відносно функцій (, g та h.

2. Функцiя N\x263Cv((, g) алгоритмiчно обчислювана відносно функцій (, g та відносно скінченноіменних операцій врізки на VA і відносно V-ІМ над A як функцій .

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

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

5. Кожна програмована на N еквітонна V-фінарна функцiя алгоритмiчно обчислювана .

, називається примiтивною програмною алгеброю програмованих на N еквітонних V-квазиарних функцiй (ППА-EQ-N).

, називається примiтивною програмною алгеброю програмованих на N еквітонних V-фінарних функцій (ППА-EФ-N).

, а також допомiжних символiв (, ) та , .

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

(t0, t1, ..., tn) \xF02D ОТ;

3) якщо t0, t1 та t2 \xF02D ОТ, то N((t0, t1, t2) \xF02D ОТ;

4) якщо t0 та t1 \xF02D\xF020ОТ, то N\x263Cv(t0, t1) \xF02D ОТ.

Кожна програмована на N еквітонна V-квазиарна функція є значенням деякого ОТ ППА-EQ-N. При інтерпретації символів на множині Nef дістаємо, що кожна програмована на N еквітонна V-фінарна функція є значенням деякого ОТ алгебри ППА-EQ-N.

Зрозуміло, що подання програмованих на N еквітонних V-квази-арних функцій операторними термами ППА-EQ-N неоднозначне.

Логiчнi операцiї над предикатами засобами ППА-EQ-N можна промоделювати таким чином:

, 1, (), Sx,y((xy, (, () та Sx,y(+xy, (, () можна відповідно трактувати як предикати ((, (&( та (((.

Враховуючи, що ((( можна подати як ((((, ((( можна подати як (((()&((((), легко отримати функції, які моделюють вказані предикати.

Вкажемо приклади програмованих на N еквітонних V-квазиарних функцій. Зрозуміло, що при обмеженні на клас V-фінарних функцій вони будуть прикладами програмованих на N V-фінарних функцій.

Приклад 1. Функції-константи програмовані.

Справді, такі функції можна отримати із базових функцій за допомогою операцій суперпозиції. Наприклад, константа 1 подається операторним термом Sx(sх, о), який позначаємо 1.

Приклад 2. Функції пsgх та sgх програмовані.

, 1, пsgх), який позначимо sgх .

Приклад 3. Функцiя |x-у| програмована.

).

Приклад 4. Предикат x>y програмований.

.

Приклад 5. Предикати x(y, x=y та x(y програмовані.

; предикат x=y моделюється функцiєю 1-|x-у|, його ж можна подати у вигляді (x(y)&(y(x); предикат x(у можна подати у вигляді ((x=у) або у вигляді (x>y)(( у>х).

.