Рекурсивная Функция

ч а с т и ч н о р е к у р с и в н а я ф у н к ц и я,- одно из математич. Уточнений интуитивного понятия вычислимой функции, определяемое следующим образом. Рассматриваются функции, заданные на натуральных числах и с натуральными значениями. Функции предполагаются частичными, т. Е. Определенными, вообще говоря, не для всех значений аргументов. Следующие функции наз. П р о с т е й ш и м и. 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наз. Ее гёделевым номером. Всюду определенные Р. Ф. Наз. О б щ е р е к у р с и в н ы м и. Существуют Р. Ф., к-рые не могут быть продолжены до общерекурсивных. Для любой Р.