Функції, елементарні за Кальмаром

Функція f(х,у) отримується з функції g(х,у) за допомогою операції сумування, якщо для всіх х, у є N маємо .

Функція f(х,у) отримується з функції g(х,у) за допомогою операції мультиплікації, якщо для всіх х, у є N маємо .

Функція f(x1, ..., xn) елементарнa (елементарнa за Кальмаром), якщо вона може бути отримана з функцій s,I , + та за допомогою скінченної кількості застосувань операцій суперпозиції, сумування і мультиплікації.

Наступні співвідношення встановлюють елементарність відомих функцій:

1) о(x) = х х;

2) ;

3) (х) = s(о(х));

4) =

5) sg(x) = x (х 1);

6) nsg(x) = 1(х) х;

8) mod(х, у) = х (у х / у])

9)C(x, y)=[((x+y)2 + 3*x+y)/2];

10) x! =xi=1 i

11) xy=yi=1 I21(x,i).

Нехай f(х) отримана за допомогою операції кускового завдання з функцій g1(x), ..., gn(x) та допоміжних функцій α1(x), ..., αn(x): f(х) = g1(x)×nsg(α1(x))+...+gn(x)×nsg(αn(x)).

Тоді f(х) – елементарна функція, якщо функції gi(x), αi(x), де 1£ i £n, елементарні.

Нехай f(х) = μy£α(x)(g(х, у)=0) отримана за допомогою операції обмеженої мінімізації. Тоді функцію f(х) можна задати у вигляді f(х)=h(х,α(x)), де .

Звідси f(х) елементарна функція, якщо функції g(х,у) та α(x) елементарні.

Кажуть, що функція f(х,у) отримується за допомогою операції обмеженої рекурсії з функцій g(х), h(х, у, z) та φ(х, у), якщо:

1) функція f(х, у) задається схемою примітивної рекурсії f(х, 0) = g(х), f(х, у) = h(х, у 1), f(х, у 1)),

2) для всіх х, уєN маємо f(х, у)£φ (х, у).


Теорема.
Нехай функція f(х, у) отримана за допомогою операції обмеженої рекурсії з функцій g(х), h(х, у, z) та φ(х, у), причому функції g(х), h(х,у,z) та φ(х,у) – елементарні. Тоді f(х, у) також елементарна.

Визначимо операцію обмеженої рекурсії в загальному випадку. Нагадаємо, що є скороченим позначенням послідовності x1, ..., xn

Скажемо, що функція f( , у) отримана за допомогою операції обмеженої рекурсії з функцій g( ), h( , у, z) та φ( , у), якщо вона задана схемою примітивної рекурсії

f( , 0) = g( ), f( , у) = h( ,у 1), f( ,у 1)),

причому для всіх єNn та уєN маємо f( , у) £ φ( , у).

Має місце природне узагальнення теореми 9.1.1.

Теорема. Нехай функція f( , у) отримана за допомогою операції обмеженої рекурсії з елементарних функцій g( ), h( , у, z) та φ( , у). Тоді функція f( , у) також елементарна.