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

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

Алфавіт:

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

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

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

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

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

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

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

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

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

Доведення:

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

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

o .

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