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

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-КЧРФ еквітонна.

, Ry,z та My , назвемо алгеброю V-КЧРФ.

, Ry,z та My , назвемо алгеброю V-ФЧРФ.

, а також допомiжних символiв (, ) та , . Дамо iндуктивне визначення ОТ алгебри V-КЧРФ:

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

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

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

4) якщо t \xF02D\xF020ОТ, то My (t) \xF02D ОТ.

Інтерпретуючи символи на множині (q природним чином, маємо: кожна V-КЧРФ є значенням деякого ОТ алгебри V-КЧРФ.

При інтерпретації символів на множині (f дістаємо, що кожна V-ФЧРФ є значенням деякого ОТ алгебри V-КЧРФ.

Якщо функцiя f є значенням ОТ (, то кажуть, що ( \xF02D опера-торний терм функцiї f, або що f задана операторним термом (.

Зауважимо, що завдання V-КЧРФ та V-ФЧРФ операторними тер-мами не є однозначним. Наприклад, операторнi терми о, Sх(о, sх), Sх(о, о) та Sх,у(о, о, s) задають одну i ту ж функцiю о.

Розглянемо приклади V-КЧРФ. Зрозуміло, що при обмеженні на клас V-ФЧРФ це будуть приклади V-ФЧРФ.

Приклад 1. Функцiї-константи \xF02D V-КЧРФ.

Справдi, константи 0, 1, 2, ... задаються відповідно операторними термами о, Sх(sх, о), Sх(sх, Sх(sх, о)), ... Операторні терми для констант 1, 2, ..., k, ... позначатимемо відповідно 1, 2, ..., k, ...

Приклад 2. Функція додавання +xy є V-КЧРФ.

Функцiя +xy визначається так: +xy (d)=’x(d)+’y(d). Зрозуміло, що значення +xy (d) визначене ( x(іт(d) та y(іт(d).

Нехай x(іт(d) та y(іт(d). Тоді маємо

+xy(d(у(0)=’x(d(у(0(z(0)=’x(d);

+xy(d(у(b+1)=sz(d(у(b(z(+xy(d(у(b)).

Отже, функція +xy утворена із базових функцій ’x та sz за допомогою операції Ry,z .

Операторний терм для функції +xy має вигляд Ry,z(’x, sz). Такий терм позначимо (xy .

Приклад 3. Функція множення (xy є V-КЧРФ.

Функцiя (xy визначається так: (xy (d)=’x(d)(’y(d). Зрозуміло, що значення (xy (d) визначене ( x(іт(d) та y(іт(d).