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

ч а с т и ч н о р е к у р с и в н а я ф у н к ц и я,- одно из математич. уточнений интуитивного понятия вычислимой функции, определяемое следующим образом. Рассматриваются функции, заданные на натуральных числах и с натуральными значениями. Функции предполагаются частичными, т. е. определенными, вообще говоря, не для всех значений аргументов. Следующие функции наз. п р о с т е й ш и м и: S(x)=x+1, о(x)=0, [img: http://localhost:8080/file/041876-8.jpg]. Будем говорить, что n-местная функция yполучена из m-местной функции j и n-местных функций f1,...,fm с помощью о п е р а т ор а с у п е р п о з и ц и и, если для всех x1...,xn имеет место равенство [img: http://localhost:8080/file/041876-9.jpg] Скажем, что (n+1)-местная функция f получается из n-местной функции j и (n+2)-местной функции y с помощью о п е р а т о р а п р и м и т и в н о й р ек у р с и и, если при любых значениях х 1,..., х п, у выполняются равенства [img: http://localhost:8080/file/041876-10.jpg] Будем говорить, что n-местная функция f получается из (n+1)-местной функции j с помощью о п е р а т ор а м и н и м и з а ц и и, или наименьшего числа оператора, если для любых x1,...,х п, у выполнено условие f (х 1,..., х п)=у тогда и только тогда, когда значения [img: http://localhost:8080/file/041876-11.jpg] определены и не равны 0, а j (х 1,..,,х n, у)=0. Частичная функция f наз. р е к у р с и в н о й, если она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации. Иными словами, f является Р. ф., если существует такая конечная последовательность частичных функций [img: http://localhost:8080/file/041876-12.jpg], что [img: http://localhost:8080/file/041876-13.jpg] и каждая функция этой последовательности либо является простейшей, либо получается из предыдущих с помощью операторов суперпозиции, примитивной рекурсии или минимизации. С помощью метода арифметизации можно получить пересчет всех таких описаний Р. ф., а именно, можно указать алгоритм, к-рый каждому натуральному числу хсопоставляет нек-рое описание Р. ф. Задаваемую этим описанием Р. ф. обычно обозначают jx,a xназ. ее гёделевым номером. Всюду определенные Р. ф. наз. о б щ е р е к у р с и в н ы м и. Существуют Р. ф., к-рые не могут быть продолжены до общерекурсивных. Для любой Р. [img: http://localhost:8080/file/041876-14.jpg] и [img: http://localhost:8080/file/041876-15.jpg] с помощью конечного числа применений операторов суперпозиции и минимизации.