РЕКУРСИВНЫЕ ФУНКЦИИ

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

При введении класса эффективно вычислимых функций естественно возникает вопрос об уточнении класса конструктивных объектов, на которых эти функции определены. Класс всех таких объектов очень обширный и трудно обозримый. В то же время при помощи метода арифметизации (см. Арифметизация метаматематики), предложенного австр. математиком К. Гёделем (р. 1906), все такие объекты легко сводятся к натуральным числам. Поэтому Р. ф. были введены как функции, определенные на мн-ве натуральных чисел и принимающие значения из того же множества. Перенесение понятий и методов, выработанных в теории Р. ф., на функции, определенные на более сложных конструктивных областях (мн-ва слов некоторого алфавита, формул некоторой теории, графов и т. п.), не представляет принципиальных затруднений.

Введем понятия, необходимые для матем, определения класса Р. ф. Везде в дальнейшем под словом «функция» понимается функция,

определенная на множестве натуральных чисел, значениями которой являются натуральные числа. Пусть ф-ции

принимают, по определению, следующие значения:

Говорят, что ф-ция возникает из ф-ций суперпозицией, если Ф-ция возникает из ф-ций примитивной рекурсией, если для всех натуральных значений у имеем

Обозначим через наименьшее значение а, для которого . Будем считать, что не определено, если: 1) значения определены для всех но отличны от а значение не определено значения определены для всех и отличны от . Таким образом, значение НУ является ф-цией от переменных Говорят, что эта ф-ция получена из ф-ции при помощи операции минимизации. Ф-ция наз. примитивно рекурсивной, если ее можно получить из ф-ций конечным числом операций суперпозиции и примитивной рекурсии; она наз. частично рекурсивной, если получена из указанных ф-ций при помощи конечного числа операций суперпозиции, примитивной рекурсии и минимизации. Всюду определенная частично Р. общерекурсивной.

Р. ф., выступая как эквивалент понятия эффективно вычислимых ф-ций, с момента их введения подверглись интенсивному исследованию. Прежде всего в классе всех Р. ф. были выделены и изучены подклассы более простых ф-ций — примитивно рекурсивных, элементарных по Л. Кальмару и др. Доказано, что класс общерекурсивных ф-ций шире класса примитивно рекурсивных: существуют общерекурсивные ф-ции, не являющиеся примитивно рекурсивными. Очевидно, что класс частично Р. ф. шире класса общерекурсивных ф-ций. Доказана также теорема о том, что любая частично Р. ф. может быть представлена в виде

примитивно Р. т. е., что для получения любой частично Р. ф. оператор можно применять не более одного раза.

Предпринимались попытки классифицировать Р. ф. Классификацию примитивно Р. ф. осуществил польский математик А. Гжегорчик (р. 1922), а классификацию, основанную на понятии сводимости (в алгоритмов теории), выполнил амер. математик Э. Пост (1897— 1954).

Исследовались также алгебры Р. на множестве Р. ф. определялись те или иные операции, относительно которых мн-ва ф-ций образовали алгебры универсальные. В качестве таких операций выбирались операции суперпозиции сложения а также операция обращения определенная и операция итерации , определенная схемой Пусть

где означает макс. целое число, не превосходящее а. Доказано, что все одноместные примитивно Р. ф. и только они могут быть получены из ф-ций конечным числом операций сложения, суперпозиции и итерации. Аналогично, каждую общерекурсивную ф-цию можно получить из ф-ций конечным числом операций сложения, суперпозиции и обращения, причем последнюю выполняют только тогда, когда результатом ее является всюду определенная ф-ция. Если же снять это ограничение, то таким способом можно получить все одноместные частично Р. ф.

Главным образом, изучились три алгебры:

где мн-ва всех одноместных примитивно рекурсивных, частично рекурсивных и общерекурсивных ф-ций. Изучались самые естественные вопросы: наличие конечных базисов, примеры подалгебр, описание макс. подалгебр, т. е. таких подалгебр, которые не содержатся ни в каких других собственных подалгебрах самих алгебр, изоморфизмы и автоморфизмы подалгебр, конгруэнции на подалгебрах, вопросы конечной определенности алгебры и др.

Вместе с изучением Р. ф. широко изучаются рекурсивные предикаты и связанные с ними множества — подмножества множества натуральных чисел. Мн-во А наз. рекурсивно перечислимым, если оно либо пусто, либо является мн-вом значений некоторой Р. ф. Мн-во А. наз. рекурсивным, если его характеристическая ф-ция является рекурсивной.

Справедливы следующие утверждения: 1) в каждом бесконечном рекурсивно перечислимом мн-ве существует рекурсивно перечислимое подмн-во с неперечислимым дополнением;

2) ф-ция является Р. ф. тогда и только тогда, когда ее график, т. е. мн-во пар вида является рекурсивно перечислимым; 3) мн-во А рекурсивно тогда и только тогда, когда оно и его дополнение рекурсивно перечислимы; 4) если А и В — рекурсивно перечислимые мн-ва, то также рекурсивно перечислимы; 5) для каждого бесконечного рекурсивно перечислимого мн-ва А существует Р. определенная на некотором подм-ве этого мн-ва, и не продолжаемая до Р. ф., определенной на всем А. Результаты, сформулированные в п. 1 и 5, лежат в основе доказательств неразрешимости многих массовых матем. проблем. Метод арифметизации языка, т. е. представления формул языка исчисления предикатов в арифметике натуральных чисел, позволил дать следующее определение разрешимости формальной теории: теория Т является разрешимой, если мн-во номеров ее теорем является рекурсивным (см. Элементарные теории, Неразрешимые алгоритмические проблемы).

Исходя из рекурсивных мн-в и предикатов, амер. математик С. Клини (р. 1904) и польский матем. А. Мостовский (р. 1913) построили иерархию мн-в и предикатов, в которой к самому низкому классу относятся рекурсивные мн-ва и общерекурсивные предикаты, а высшие классы классифицируются по виду кванторной приставки их описаний (см. Арифметическая и аналитическая иерархии).

Ф-цию универсальной для класса -местных ф-ций F, если при любом и для любой ф-ции найдется г такое, что Одним из важнейших фактов теории Р. ф. является теорема о существовании для любого частично Р. универсальной для класса всех частично рекурсивных функций.

Пусть двуместная частично Р. универсальная для класса всех одноместных частично Пусть Число i назовем номером ф-ции относительно универсальной ф-ции Очевидно, что одна и та же ф-ция может иметь много номеров. Существует такая двуместная универсальная частично т. н. клиниевская универсальная фция, что имеют место следующие теоремы: 1) теорема о неподвижной точке: какова бы ни была частично Р. ф. , существует такое число z, что номера одной и той же функции. Существует Р. ф., которая по номеру ф-ции дает соответствующее ; 2) если а непустое семейство одноместных частично Р. ф., отличное от совокупности всех таких ф-ций, То мн-во всех номеров ф-ций, принадлежащих а, не может быть рекурсивным.

Здесь рассмотрена только одна нумерация Р. осуществляемая при помощи клиниев-Ской универсальной ф-ции. Изучение различных свойств разных нумераций является предметом нумераций теории. Теория Р. ф. являйся широко разработанной матем. дисциплиной, составляющей ядро теории алгоритмов. Широко изучаются связи теории Р. ф. с программированием для ЦВМ и автоматов теорией.

Лит.: Успенский В. А. Лёкции о вычислимых функциях. М., 1960 [библиогр. с. 476—481]; Мальцев А. И. Алгоритмы и рекурсивные функции. М., 1965 [библиогр. с. 375—381]; Захаров Д. А. Рекурсивные функции. Новосибирск, 970 [библиогр. с. 201—204]; Роджерс X. Теория рекурсивных функций и эффективная вычислимость. Пер. с англ. М., 1972 [библиогр. с. 587— 599]; Эббинхауз Г. Д. [и др.]. Машины Тьюринга и рекурсивные функции. Пер. с нем. М., 1972.

М. И. Кратко.