Рекурсивные функции это:

Рекурсивные функции
(от позднелатинского recursio — возвращение)
        название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого Алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами. Р. ф. были введены в 30-х гг. 20 в. С. К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя (См. Гёдель), Ж. Эрбрана и др. математиков.
         Каждая Р. ф. задаётся конечной системой равенств точно охарактеризованного типа в том смысле, что её значения вычисляются с помощью этой системы равенств по точно формулируемым правилам, причём таким образом, что в итоге для вычисления значений заданной Р. ф. получается алгоритм определённого типа.
         Арифметические функции, для вычисления значений которых имеются какие-либо алгоритмы, принято называть вычислимыми. Вычислимые функции играют в математике важную роль. Вместе с тем, если понятию алгоритма здесь не будет придан точный смысл, то и само понятие вычислимой функции окажется несколько расплывчатым. Р. ф. уже в силу самого характера своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом несколько расплывчатого понятия вычислимости. Предложение считать понятие вычислимости совпадающим по объёму с понятием рекурсивности известно в теории Р. ф. под названием тезиса Чёрча по имени американского математика А. Чёрча, впервые (в 30-х гг. 20 в.) сформулировавшего и обосновавшего это предложение. Принятие тезиса Чёрча позволяет придать понятию вычислимой арифметической функции точный математический смысл и подвергнуть это понятие изучению при помощи точных методов.
         Р. ф. являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин «частично рекурсивные функции». Р. ф., определённые при любых значениях аргументов, называют общерекурсивными функциями.
         Определению Р. ф. может быть придана следующая форма. Фиксируется небольшое число чрезвычайно простых исходных функций, вычислимых в упомянутом выше интуитивном смысле (функция, тождественно равная нулю, функция прибавления единицы и функции, выделяющие из системы натуральных чисел член с данным номером); фиксируется небольшое число операций над функциями, переводящих вычислимые функции снова в вычислимые (операторы подстановки, примитивной рекурсии и минимизации). Тогда Р. ф. определяются как такие функции, которые можно получить из исходных в результате конечного числа применений упомянутых выше операций.
         Оператор подстановки сопоставляет функции f от n переменных и функциям g1, . . ., gn от m переменных функцию h от m переменных такую, что для любых натуральных чисел x1, .., xm
         h(x1, .., xm) ≅ f (g1(x1, .., xm), ..., gm(x1, .., xm))
        (здесь и ниже условное равенство ≅ означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение).
         Оператор примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n + 1 переменных такую, что для любых натуральных чисел x1, .. .., xn, y
         h(x1, .., xn ,0) ≅ f(x1, .., xn),
         h(x1, .., xn, y + 1) ≅ g(x1, .., xn, y, h(x1, .., xn, y )).
         Оператор минимизации сопоставляет функции f от n переменных функцию h от n переменных такую, что для любых натуральных чисел x1, .., xn
         h(x1, .., xn) ≅ f(x1, .., xn-1, y)
        где у таково, что f(x1, .., xn-1, y-1) определены и отличны от xn, а f(x1, .., xn, y) определена и равна xn, если же у с указанными свойствами не существует, то значение h(x1, .., xn) считается не определённым.
         Важную роль в теории Р. ф. играют т. н. примитивно рекурсивные функции — Р. ф., получающиеся из исходных функций в результате конечного числа применений одних лишь операторов подстановки и примитивной рекурсии. Они образуют собственную часть класса общерекурсивных функций. В силу известной теоремы Клини о нормальной форме Р. ф. могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и Tn от n + 2 переменных, что для любой Р. ф. φ от n переменных и для любых натуральных чисел x1, . . ., xn имеет место равенство φ(x1, ..., xn) ≅ U(y), где у есть наименьшее из чисел z таких, что Tn(φ, x1, ..., xn,z) = 0 (здесь φ представляет собой т. н. геделев номер функции φ — число, которое эффективно строится по системе равенств, задающей функцию φ). Из этой теоремы, в частности, вытекает, что для Р. ф. от п переменных может быть построена универсальная Р. ф. от n+1 переменных, т. е. такая Р. ф. Фn, что для любой Р. ф. φ от n переменных и для любых натуральных чисел x1, . . ., xn имеет место условное равенство
         φ( x1, . . ., xn) ≅ Фn(x1, . . ., xn).
         Это — один из центральных результатов общей теории Р. ф.
         Теория Р. ф., являясь частью алгоритмов теории (См. Алгоритмов теория), представляет собой разветвленную математическую дисциплину с собственной проблематикой и с приложениями в др. разделах математики. Понятие «Р. ф.» может быть положено в основу конструктивного определения исходных математических понятий. Широкое применение теория Р. ф. нашла в математической логике (См. Логика). В частности, понятие примитивно рекурсивной функции лежит в основе первоначального доказательства знаменитой теоремы Гёделя о неполноте формальной арифметики, а понятие «Р. ф.» в его полном объёме было использовано С. К. Клини для интерпретации интуиционистской арифметики (исследование это составило целую эпоху в области семантики (См. Семантика)). Аппарат теории Р. ф. используется также в теории вычислительных машин и программирования.
         Исследования показали, что все известные уточнения общего понятия алгоритма, в том числе Р. ф., взаимно моделируют друг друга и, следовательно, ведут к одному и тому же понятию вычислимой функции. Это обстоятельство служит серьёзным доводом в пользу тезиса Чёрча.
         Лит.: Клини С. К., Введение в математику. пер. с англ., М., 1957; Успенский В. А., Лекции о вычислимых функциях, М., 1960; Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; Роджерс Х., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972.
         Н. М. Нагорный.

Большая советская энциклопедия. — М.: Советская энциклопедия. 1969—1978.

Смотреть что такое "Рекурсивные функции" в других словарях:

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

  • рекурсивные функции — (лат. recursio возвращение) такие функции, значения которых для данного аргумента вычисляются с помощью значений для предшествующих аргументов; термин, употребляемый в современных исследованиях по основаниям арифметики. Новый словарь иностранных… …   Словарь иностранных слов русского языка

  • РЕКУРСИВНЫЕ ФУНКЦИИ И ПРЕДИКАТЫ — один из важнейших для оснований математики и математич. логики классов понятий, служащих уточнениями содержат. понятий эффективно вычислимой арифметической функции и эффективно разрешимого арифметического предиката, а в конечном счете, – и… …   Философская энциклопедия

  • РЕКУРСИИ ВЫСШИХ СТУПЕНЕЙ — рекурсивные определения, в к рых в качестве вспомогательных объектов наряду с числовыми функциями используются нек рые функционалы более высоких типов. Напр., для случая рекурсии второй ступени таковыми являются подстановочные функционалы вида а… …   Математическая энциклопедия

  • Примитивно рекурсивная функция — Термин рекурсивные функции в теории вычислимости используют для обозначения трёх множеств функций примитивно рекурсивные функции; общерекурсивные функции; частично рекурсивные функции. Последние совпадают с множеством вычислимых по Тьюрингу… …   Википедия

  • Частично рекурсивная функция — Термин рекурсивные функции в теории вычислимости используют для обозначения трёх множеств функций примитивно рекурсивные функции; общерекурсивные функции; частично рекурсивные функции. Последние совпадают с множеством вычислимых по Тьюрингу… …   Википедия

  • Общерекурсивная функция — Термин рекурсивные функции в теории вычислимости используют для обозначения трёх множеств функций примитивно рекурсивные функции; общерекурсивные функции; частично рекурсивные функции. Последние совпадают с множеством вычислимых по Тьюрингу… …   Википедия

  • Рекурсивная функция (теория вычислимости) — У этого термина существуют и другие значения, см. Рекурсивная функция (значения). Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций примитивно рекурсивные функции; общерекурсивные функции; …   Википедия

  • РЕКУРСИЯ — способ определения функций, являющийся объектом изучения в теории алгоритмов и других разделах математич. логики. Этот способ давно применяется в арифметике для определения числовых последовательностей (прогрессии, чисел Фибоначчи и пр.).… …   Математическая энциклопедия

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

Книги

Другие книги по запросу «Рекурсивные функции» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»