РЕКУРСИВНАЯ ФУНКЦИЯ

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

. Будем говорить, что n-местная функция yполучена из m-местной функции j и n-местных функций f₁,. . .,f_m с помощью о п е р а т ор а с у п е р п о з и ц и и, если для всех x₁. . .,x_n имеет место равенство

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

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

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

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

Для любой Р. <ф. можно указать алгоритм вычисления ее значений, т. е. все Р. ф. суть вычислимые функции. Распространенная гипотеза, известная под названием т е з и с а Ч ё р ч а, состоит в том, что всякая вычислимая функция является Р. ф. Эта гипотеза подтверждается рядом фактов. Так, все рассматривавшиеся в математике конкретные функции, признаваемые вычислимыми в интуитивном смысле этого слова, оказывались рекурсивными. Понятие Р. ф. оказывается совпадающим по объему с другими математич. уточнениями понятия вычислимой функции (напр., с понятиями функции, вычислимой на машине Тьюринга, вычислимой с помощью нормального алгорифма Маркова и др.). Возможны различные определения класса всех Р. ф. через исходные функции и порождающие операции. В частности, всякая Р. <ф. может быть получена из функций

и

с помощью конечного числа применений операторов суперпозиции и минимизации.

Лит.:[1] М а л ь ц е в А. И., Алгоритмы и рекурсивные функции, М., 1965; [2] Р о д ж е р с X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972.

В. Е. Плиско.