11.1. Примитивно рекурсивные функции

Программы с коночным числом переменных напоми­нали ассемблер; рассматриваемые в этом разделе рекур­сивные функции скорее напоминают функциональное программирование, когда одни функции определяются через другие. Мы будем рассматривать функции с на­туральными аргументами и значениями. Вообще говоря, функции могут быть но всюду определенными, так что говоря о функции п аргументов (функции из М™ в М, п-местной функции), мы имеем в виду функцию, опре­делённую на некотором подмножество М™ со значениями в N.

Пусть имеется й-местная функция f ж к штук п-мест-ных функций д\,... ,дк. Тогда из них можно сформиро­вать одну п-местную функцию

(хг,. ..,хп) н->- /(ді(хі,. ..,хп),. ..,дк(хі,... ,хп)).

Говорят, что определённая таким образом функция по­лучена из функций / и д\,... ,дк е помощью операции подстановки.

Другая операция, называемая операцией рекурсии, или примитивной рекурсии, применяется к й-местной функции / и (к + 2)-местной функции д. Её результатом будет (к + 1)-местная функция К, определяемая так:

Щхі,... ,хк,0) = f(xl,... ,хк); Щхі,... ,хк,у+1) = д(хі,... ,хк,у,Щхі,... ,хк,у)).

В последовательности к(х\,..., хп, 0), к(х\,..., хп, 1),... каждое значение определяется через предыдущее, поэто­му если какое-то из значений но определено, то но опре­делены и все последующие.

Для единообразия будем считать, что нуль-местные функции (функции без аргументов) суть константы; это позволяет рекурсивно определять функции одной пере­менной.

Примитивно рекурсивными называют функции, кото­рые можно получить с помощью операций подстановки и рекурсии из следующих базисных функций: константы О, операции прибавления единицы в: х ^ х -\- 1 ж семейства функций проекции: это семейство для каждого к содер­жит к ШТуК Й-МеСТНЫХ фуНКЦИЙ Ж1к(х\, . . . , Хк) = Х{.

Функции проекции позволяют выполнять «неодно­родные» подстановки: скажем, можно получить функ­цию (х,у) I—У /(д(х),к(у,х,у),х) из функций f ж к, комбинируя их с функциями проекции: сначала полу­чаем функцию (х,у) I—У д(х) (подстановка ж\ в д), за­тем (х,у) I—У к(у, х, у) (подстановка ж\,ж\, ж\ в Щ, затем полученные две функции вместо с функцией ж\ подста­вляем в /.

Подставляя константу 0 в функцию прибавления еди­ницы, получаем константу (функцию нуля аргументов) 1. •Затем можно получить константы 2, 3 и т.д.