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

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

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

Функція f(x₁,..., x_n) елементарн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)² + 3*x+y)/2];

10) x! =^x∏_i=1 i

11) x^y=^y∏ _i=1 I²₁(x,i).

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

Тоді f(х) – елементарна функція, якщо функції g_i(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(х, у) також елементарна.

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

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

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

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

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

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