Математическая энциклопедия - рекурсивная функция

ч а с т и ч н о р е к у р с и в н а я ф у н к ц и я,одно из математич. уточнений интуитивного понятия вычислимой функции, определяемое следующим образом. Рассматриваются функции, заданные на натуральных числах и с натуральными значениями. Функции предполагаются частичными, т. е. определенными, вообще говоря, не для всех значений аргументов. Следующие функции наз. п р о с т е й ш и м и: S(x)=x+1, о(x)=0,

. Будем говорить, что n-местная функция yполучена из m-местной функции j и n-местных функций f1,. . .,fm с помощью о п е р а т ор а с у п е р п о з и ц и и, если для всех x1. . .,xn имеет место равенство

Скажем, что (n+1)-местная функция f получается из n-местной функции j и (n+2)-местной функции y с помощью о п е р а т о р а п р и м и т и в н о й р ек у р с и и, если при любых значениях х 1,. . ., х п, у выполняются равенства

Будем говорить, что n-местная функция f получается из (n+1)-местной функции j с помощью о п е р а т ор а м и н и м и з а ц и и, или наименьшего числа оператора, если для любых x1,. ..,х п, у выполнено условие f (х 1,. . ., х п)=у тогда и только тогда, когда значения определены и не равны 0, а j (х 1,. . ,,х n, у)=0. Частичная функция f наз. р е к у р с и в н о й, если она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации.

Иными словами, f является Р. ф., если существует такая конечная последовательность частичных функций , что и каждая функция этой последовательности либо является простейшей, либо получается из предыдущих с помощью операторов суперпозиции, примитивной рекурсии или минимизации. С помощью метода арифметизации можно получить пересчет всех таких описаний Р. ф., а именно, можно указать алгоритм, к-рый каждому натуральному числу хсопоставляет нек-рое описание Р. ф. Задаваемую этим описанием Р. ф. обычно обозначают jx,a xназ. ее гёделевым номером.

Всюду определенные Р. ф. наз. о б щ е р е к у р с и в н ы м и. Существуют Р. ф., к-рые не могут быть продолжены до общерекурсивных.

Для любой Р.