Рекурсия

Способ определения функций, являющийся объектом изучения в теории алгоритмов и других разделах математич. логики. Этот способ давно применяется в арифметике для определения числовых последовательностей (прогрессии, чисел Фибоначчи и пр.). Существенную роль играет Р. в вычислительной математике (рекуррентные методы). Наконец, в теории множеств часто используется трансфинитная Р. Долгое время термин "Р" употреблялся математиками, не будучи точно определенным. Его приблизительный интуитивный смысл можно описать следующим образом. Значение искомой функции f в произвольной точке (под точкой подразумевается набор значений аргументов) определяется, вообще говоря, через значения этой же функции в других точках к-рые в каком-то смысле "предшествуют" . (Само слово "рекурсия" означает "возвращение".) Конечно, в нек-рых "исходных" точках значения f должны задаваться непосредственно. Иногда при помощи Р. определяются одновременно несколько функций; тогда вышеприведенные разъяснения нуждаются в соответствующей модификации. Примеры разнообразных Р. будут даны ниже. Отношение предшествует (где принадлежат области определения искомой функции) в разных видах Р. ("рекурсивных схемах") может иметь разный смысл, однако оно должно быть "фундированным" (т. е. не должно существовать бесконечной последовательности точек такой, что предшествует ). Кроме того, неявно подразумевается, что оно является "достаточно естественным" (напр., желательно, чтобы это отношение усматривалось из самого описания рекурсивной схемы, а не из процесса ее применения). Последнее условие имеет чисто эвристич. значение (напр., для определения каких-нибудь специальных, сравнительно простых видов Р.). Уточнение этого условия по существу неотделимо от уточнения самого понятия Р., а для этого необходимо установить, какого рода формальные выражения могут быть признаны в качестве рекурсивных определений. В тех случаях, когда речь идет о рекурсивных описаниях числовых функций (т. е. функций от натуральных аргументов и с натуральными значениями), обычно подразумевается, что такие описания задают способ вычисления определяемых функций. Ниже всюду (кроме заключительных замечаний) термин "Р." будет пониматься именно в таком смысле. Простейшей и наиболее употребительной рекурсивной схемой является примитивная Р.: где функции g, h предполагаются известными, f — определяемая функция, у — переменная, по к-рой ведется P., x1,. . ., х п — параметры, не участвующие в Р. Ближайшим обобщением этой схемы является т. н. в о з в р а т н а я Р., охватывающая такие виды рекурсивных определений, у к-рых, подобно примитивной P., только одна переменная участвует в Р., а соответствующее отношение предшествования совпадает с обычным упорядочением натуральных чисел (иногда, впрочем, этот термин употребляется и в более широком смысле). Наиболее типичная разновидность в о з в р а тн о й Р. такова: где . Представляет интерес тот факт, что возвратную Р. можно заменить конечным числом примитивных Р. и подстановок. Другой пример рекурсивной схемы, сводящейся к примитивной Р., даст о д н о в р е м е н н а я Р. вида где i=l,. . ., k. Математич. логика часто имеет дело с п р и м и т и в н о р е к у р с и в н ы м и функциями, т. е. с такими, к-рые можно получить за конечное число шагов при помощи подстановок и примитивных Р., исходя из нек-рого фиксированного запаса совсем простых функций (напр., и т. п.). Последовательность функциональных равенств, описывающая такое построение, наз. примитивно р е к у р с и в н ы м о п и с а н и е м соответствующей функции. Эти описания суть синтаксич. объекты (т. с. цепочки символов), обладающие определенной эффективно распознаваемой структурой. Практически все числовые функции, употребляемые в математике по какому-либо конкретному поводу, оказываются примитивно рекурсивными. Этим в значительной мере объясняется интерес к данному классу функций. Более сложные виды рекурсивных определений получаются, когда Р. идет сразу по нескольким переменным. Такие определения, вообще говоря, выводят из класса примитивно рекурсивных функций, хотя соответствующее отношение предшествования может выглядеть как вполне естественное. Напр., в определении f(x, у )могут участвовать значения f(u, v), где u<xили и=х, v<y, как это имеет место в следующей схеме д в ук р а т н о й Р.: Эта схема уже не сводится к примитивной Р. С другой стороны, к ней сводимы многие более сложные рекурсивные определения (см. [1]). Перечисленные частные виды Р. имеют точные математич. определения — в отличие от расплывчатых "около математических" представлений о "рекурсии вообще". Уточнение этих представлений естественно мыслить как отыскание подходящего алгоритмич. языка (т. е. формального языка для описания вычислительных процедур), включающего все вообразимые виды Р., но и не слишком широкого. Правомерно ожидать, что выработка такого уточнения может потребовать дополнительных соглашений, вносящих нечто новое в интуитивное понимание Р. В этой связи небезинтересно отметить, что все рассмотренные выше рекурсивные схемы ориентированы на порождение тотальных (всюду определенных) функций. Так, если в схеме примитивной рекурсии g, h тотальны, то такова же и f. И вообще, рекурсивные определения, задающие частичные функции, с интуитивной точки зрения выглядят несколько искусственно. Однако есть причины привлечь такие Р. к рассмотрению. Это связано с т. н. диагональным методом. Именно, пусть дан алгоритмич. язык L, в к-ром определимы лишь тотальные функции, и пусть синтаксич. конструкции Lне выводят за пределы интуитивно понимаемой рекурсивности. Конечно подразумевается, что выражения языка L(являющиеся описаниями функций) алгоритмически распознаваемы и что имеется единообразный способ вычисления функций, представимых в L, по их описаниям. Если рассматривать выражения в Lпросто как цепочки символов, то каждую такую цепочку можно считать изображением натурального числа в подходящей системе счисления, являющегося "кодом" данного выражения. Пусть теперь функция G(m,х )определена так. Если m есть код описания (в языке L)нек-рой одноместной функции fm, то В противном случае , где j — какая-нибудь фиксированная функция, представимая в L. Ясно, что G(m,x )вычислима и тотальна и такова же функция . Но Fневыразима в L, ибо ни при каком тневозможно равенство (В этом рассуждении существенно использована тотальность F. )Возникает вопрос: является ли данное описание Fрекурсивным? Если в качестве L взять язык примитивно рекурсивных описаний, то оно оказывается сводимым к двукратной Р. В общем случае ситуация неясна из-за расплывчатости интуитивных представлений о Р., так что положительный ответ на поставленный вопрос представляет собой дополнительное соглашение. Если принять его (как это неявно делает современная логика), то язык L, описывающий в точности все виды "тотальной" Р., оказывается невозможным. Между тем, если в L выразимы также частичные функции (и их описания признаются рекурсивными), то диагонализация не обязательно выводит за пределы L, так что такой язык в принципе может быть пригодным для адекватного уточнения рскурсивности. Правда, это связано с нек-рым переосмыслением самого понятия Р., и современное строгое определение этого понятия не вполне согласовано с имевшимися ранее интуитивными представлениями. В новом уточненном смысле Р. есть нек-рая синтаксич. операция (с фиксированной интерпретацией), употребляемая для построения выражений в различных алгоритмич. языках. Если L- один из таких языков, то естественно предполагать, что в нем есть и другие синтаксич. операции, от к-рых зависит конкретный вид рекурсивных описаний в L. Вообще говоря, выражения языка Lне обязательно описывают только числовые функции. Нек-рые из них могут задавать функциональные операторы и другие объекты. Это нужно, в частности, для определения Р. Рекурсивные описания в L — это системы функциональных уравнений вида , где fi- — определяемые функции, а Т i — выражения в L, задающие в совокупности нек-рый оператор. Но все выразимые в L операторы должны быть эффективными (поскольку L- алгоритмич. язык) и потому монотонными (т. е. они сохраняют отношение , означающее, что y) доопределяет j). В силу этого всякая система указанного вида обладает минимальным (в смысле отношения ) решением и, по определению, является рекурсивным описанием функций, составляющих это решение. Исходя из данного описания, искомое минимальное решение можно получить посредством следующего процесса. Для i=l, ... , ппусть — нигде не определенная функция и , так что . Нетрудно убедиться, что искомые функции fi- получаются "объединением" . Тем самым задан способ совместного вычисления fi-. Этот же процесс задает более или менее естественное отношение предшествования на аргументах, к-рое и оправдывает (в удовлетворительной мере) употребление термина "Р." в данной связи. Для того чтобы приведенные ранее рекурсивные схемы подходили под такое определение, необходимо, чтобы язык Lбыл не слишком беден. Так, уже в случае примитивной Р. нужны подстановка и "кусочное" определение (т. е. задание функции несколькими равенствами). Вместе с тем этих двух синтаксич. операций, в сочетании с только что определенной Р., уже достаточно для получения всех вычислимых функций (исходя из простейших). При соответствующих предположениях об Lможно также достаточно уверенно утверждать, что данное определение Р. охватывает все интуитивно мыслимые рекурсивные описания. В то же время введенное общее определение обладает характерными чертами неформально понимаемой рекурсивности, к-рые признаются существенными в современной математике. Плодотворность данного определения Р. заключается не только в его значении для теории алгоритмов, но и в том, что оно позволяет взглянуть с "алгоритмической" (в обобщенном смысле) точки зрения также и на нек-рые конструкции абстрактной математики, имеющие определенное сходство с "числовыми" Р. (трансфинитная Р., индуктивные определения, рекурсивные иерархии и т. п.). Лит.:[1] П е т е р Р., Рекурсивные функции, пер. с нем., М., 1954; [2] М а л ь ц е в А. И., Алгоритмы и рекурсивные функции, М., 1965; [3] У с п е н с к и й В. А., Лекции о вычислимых функциях, М., I960; [4] К л и н и С. К., Введение в метаматематику, пер. с англ., М., 1957; [5] М о s с h о v ak i s Y. N., Elementary induction on abstract structures, Amst.,- [a. o.], 1974. Н. В. Белякин.