| ние), название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметич. алгоритма, т. е. такого алгоритма, допустимые исходные данные к-рого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами. Р. ф. были введены в 30-х гг. 20 в. С. К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя, Ж. Эрбрана и др. математиков.
Каждая Р. ф. задаётся конечной системой равенств точно охарактеризованного типа в том смысле, что её значения вычисляются с помощью этой системы равенств по точно формулируемым правилам, причём таким образом, что в итоге для вычисления значений заданной Р. ф. получается алгоритм определённого типа.
Арифметич. функции, для вычисления значений к-рых имеются к.-л. алгоритмы, принято называть вычислимыми. Вычислимые функции играют в математике важную роль. Вместе с тем, если понятию алгоритма здесь не будет придан точный смысл, то и само понятие вычислимой функции окажется неск. расплывчатым. Р. ф. уже в силу самого характера своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом неск. расплывчатого понятия вычислимости. Предложение считать понятие вычислимости совпадающим по объёму с понятием рекурсивности известно в теории Р. ф. под названием тезиса Чёрча по имени амер. математика А. Чёрча, впервые (в 30-х гг. 20 в.) сформулировавшего и обосновавшего это предложение. Принятие тезиса Чёрча позволяет придать понятию вычислимой арифметич. функции точный математич. смысл и подвергнуть это понятие изучению при помощи точных методов.
Р. ф. являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин "частично рекурсивные функции". Р. ф., определённые при любых значениях аргументов, наз. общерекурсивными функциями.
Определению Р. ф. может быть придана следующая форма. Фиксируется небольшое число чрезвычайно простых исходных функций, вычислимых в упомянутом выше интуитивном смысле (функция, тождественно равная нулю, функция прибавления единицы и функции, выделяющие из системы натуральных чисел член с данным номером); фиксируется небольшое число операций над функциями, переводящих вычислимые функции снова в вычислимые (операторы подстановки, примитивной рекурсии и минимизации). Тогда Р. ф. определяются как такие функции, к-рые можно получить из исходных в результате конечного числа применений упомянутых выше операций.
Оператор подстановки сопоставляет функции f от п переменных и функциям g1, . . ., gnот т переменных функцию h от m переменных такую, что для любых натуральных чисел
x1, . . ., xm h(x1, ..., xm) ~ f(g1(x1, ..., xm), ..., gm(x1, ..., xm))
(здесь и ниже условное равенство ~; означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение).
Оператор примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n +1 переменных такую, что для любых натуральных чисел
x1, . . ., xп, y h(x1, ..., хn, 0) ~ f(x1, ..., хn), h(x1, ..., хn, у + 1) ~ g(x1, ..., хn, у, h(x1, ..., хn, y)).
Оператор минимизации сопоставляет функции f от п переменных функцию h от п переменных такую, что для любых натуральных чисел x1, ..., хn
h(x1, ..., хn) =: f(x1, ..., хn-1, y),
где у таково, что f(x1, ..., хn-1, 0), ... . . ., f(x1, ..., хn-1, y-1) определены и отличны от хn, a f(x1, ..., хn-1, у) определена и равна хп; если же у с указанными свойствами не существует, то значение h(x1, ..., хn) считается не определённым.
Важную роль в теории Р. ф. играют т. н. примитивно рекурсивные функции - Р. ф., получающиеся из исходных функций в результате конечного числа применений одних лишь операторов подстановки и примитивной рекурсии. Они образуют собств. часть класса общерскурсивных функций. В силу известной теоремы Клини о нормальной форме Р. ф. могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и Тn от n + 2 переменных, что для любой Р. ф. ф от и переменных и для любых натуральных чисел x1, . . ., хn имеет место равенство fp(x1, . . ., xn)~=U(y), где у есть наименьшее из чисел z таких, что
Тn (ф, x1, . . ., Хп, z) = 0 (здесь ф представляет собой т. н. гёделев номер функции ф - число, к-рое эффективно строится по системе равенств, задающей функцию ф). Из этой теоремы, в частности, вытекает, что для Р. ф. от и переменных может быть построена универсальная Р. ф. от n + 1 переменных, т. е. такая Р. ф. Фn, что для любой Р. ф. ф от п переменных и для любых натуральных чисел х1, . . ., хn имеет место условное равенство
ф(x1, .... xn) ~ Фn(ф, x1, ..., xn).
Это - один из центральных результатов общей теории Р. ф.
Теория Р. ф., являясь частью алгоритмов теории, пр |
