Співвідношення між класами примітивно рекурсивних та елементарних функцій

Нехай , де носій El – клас елементарних функцій; – це операції.

Алфавіт:

Визначення операторного терму:

1. Усі символи базових функцій є операторними термами.

2. Якщо є операторними термами для завдання m-арних функцій, а є термом для задання n-арної функції, то терм є термом для позначення m-арної функції.

3. Якщо є операторним термом для бінарної функції, то терми є операторними термами для бінарних функцій.

4. Інших оператор них термів не існує.

Зрозуміло, що кожна елементарна функція є ПРФ. Доведемо зворотне твердження – що це включення строге.

Для цього розглянемо допоміжну функцію :

Функцію назвемо k -східчастою, якщо має місце умова: .

Теорема: Довільна елементарна функція є k -східчастою для певного відповідного значення k.

Доведення:

· Базові функції:

o

o так само для ;

o .

· Нехай є операторним термом для бінарної функції . Утворимо функції та (обидві вони бінарні). Нехай є -східчастою функцією. Тоді є -східчастими функціями.

o Це випливає з двох нерівностей:

§

§

o Обидві вони доводяться математичною індукцією.

· Нехай , де - -арна функція, а - -арні. Тоді є -арною функцією.

Покажемо тепер, що існує ПРФ, яка не є елементарною.

Наприклад, візьмемо функцію . Для такої функції не існує такого єдиного , для якого можна було б мажорувати цю функцію -східчастою.