РЕКУРСИ́ВНЫЕ ФУ́НКЦИИ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
РЕКУРСИ́ВНЫЕ ФУ́НКЦИИ, один из наиболее распространённых вариантов математич. уточнения понятия вычислимой арифметич. функции, т. е. вычислимой функции, аргументы и значения которой – натуральные числа. При этом функция $f$ называется вычислимой, если существует алгоритм, перерабатывающий объект $x$, для которого определена функция $f$, в объект $f(x)$ и не приводящий к результату ни для какого $x$, для которого $f$ не определена.
Р. ф. являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин «частично рекурсивные функции». Р. ф., определённые при любых значениях аргументов, называются общерекурсивными функциями.
Определению Р. ф. может быть придана следующая форма. Фиксируется небольшое число простых исходных вычислимых функций: $O(x)=0$, $S(x)=x+1$, $I^n_m(x_1,...,x_n)=x_m$, $1⩽m⩽n$; фиксируется также небольшое число операций над функциями, переводящих вычислимые функции снова в вычислимые: операторы подстановки, примитивной рекурсии и минимизации. Оператор подстановки сопоставляет функции $f$ от $n$ переменных и функциям $g_1$, ..., $g_n$ от $m$ переменных функцию $h$ от $m$ переменных такую, что для любых натуральных чисел $x_1, ..., x_m$ $$h(x_1,...,x_m)≌\\≌f(g_1(x_1,...,x_m), ..., g_n(x_1,...,x_m))$$ (здесь и далее условное равенство $≌$ означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение). Оператор примитивной рекурсии сопоставляет двум функциям $f$ от $n$ переменных и $g$ от $n+2$ переменных такую функцию $h$ от $n+1$ переменных, что для любых натуральных чисел $x_1$, ...,$x_n$, $y$ $$h(x_1, ..., x_n,\,0)≌f(x_1, ..., x_n),\\h(x_1,...,x_n, y+1)≌\\≌g(x_1,...,x_n,\,y,\,h(x_1,...,x_n, y))$$. Оператор минимизации сопоставляет функции $f$ от $n+1$ переменных функцию $h$ от $n$ переменных такую, что для любых натуральных чисел $x_1$, ..., $x_n$, $y$ $$h(x_1, ..., x_n)=y$ тогда и только тогда, когда $f(x_1, ..., x_n,\,0)$, ..., $f(x_1, ..., x_n,\,y-1)$ определены и отличны от 0, а $f(x_1, ..., x_n,\,y)$ определена и равна 0; если же $y$ с указанными свойствами не существует, то значение $h(x_1, ..., x_n)$ считается неопределённым.
Р. ф. – это функции, которые можно получить из исходных в результате конечного числа применений операторов подстановки, примитивной рекурсии и минимизации. Р. ф. в силу своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом несколько расплывчатого представления о вычислимости. Предложение считать вычислимость совпадающей по своему объёму с понятием рекурсивности известно в теории Р. ф. под назв. «тезис Чёрча». Принятие этого тезиса позволяет придать понятию вычислимой арифметич. функции точный математич. смысл и подвергнуть это понятие изучению при помощи точных методов.
Теория Р. ф., являясь частью алгоритмов теории, представляет собой разветвлённую математич. дисциплину с собств. проблематикой и с приложениями в др. разделах математики. Понятие «Р. ф.» может быть положено в основу конструктивного определения исходных математич. понятий. Широкое применение теория Р. ф. нашла в математич. логике. В частности, понятие «примитивно Р. ф.» (они получаются из указанных выше исходных функций в результате конечного числа применений лишь операторов подстановки и примитивной рекурсии) лежит в основе первоначального доказательства теоремы Гёделя о неполноте. Аппарат теории Р. ф. используется также в теории вычислит. машин и программирования.