Рекурсивные функции.
Рекурсивная функция (частично рекурсивная функция) – функция, заданная с помощью последовательности частичных (определенных не обязательно для всех значений своих аргументов) функций таких, что каждая функция последовательности либо является (базисной) простейшей функцией, либо получена из предыдущих с помощью операторов суперпозиции (подстановки) Snm, примитивной рекурсии Rn и минимизации .
Все рекурсивные функции являются вычислимыми функциями, то есть для любой такой функции можно указать алгоритм вычисления ее значений. Очевидно, что всякий алгоритм однозначно ставит в соответствие исходным данным (в случае, если он определен на них) результат. Поэтому с каждым алгоритмом однозначно связана функция, которую он вычисляет. Однако, обратное, то есть: «для всякой функции существует вычисляющий ее алгоритм», неверно.
Согласно тезису Черча, любая функция, считающаяся вычислимой в интуитивном смысле, является рекурсивной функцией. Эта гипотеза (тезис) подтверждается тем, что все известные вычислимые функции являются рекурсивными. Тезис Черча позволяет придать интуитивному понятию вычислимой функции точный алгоритмический смысл.
Понятие рекурсивной функции эквивалентно понятию функции, вычислимой на машине Тьюринга.
В теории рекурсивных функций, рассматриваемой ниже, как и вообще в теории алгоритмов, принят конструктивный, финитный подход, основной чертой которого является то, что все множество исследуемых объектов (в данном случае функций) строится из конечного числа исходных объектов – базиса – с помощью простых операторов (операций), эффективная выполнимость которых достаточно очевидна.
Замечание:
Всюду определенные рекурсивные функции называются общерекурсивными функциями.
Примитивно-рекурсивные функции.
Def. Всюду определенная функция от натуральных аргументов с натуральными значениями, которую можно получить из простейших базисных всюду определимых функций
f(x)=x+1, z(x)=0, Jnm(x1,…, xn)=xm
Конечным числом операторов (операций) суперпозиции (подстановок) Snm, и примитивной рекурсии Rn называется примитивно-рекурсивной (ПРФ).
Базисную функцию f(x)=x+1 принято называть функцией следования (эту функцию иногда обозначают х` и называют функцией прибавления единицы), z(x)=0 – нуль функцией, Jnm(x1,…, xn)=xm – функцией тождества (или введения фиктивных переменных), где nm.
Def. Оператором суперпозиции Snm называется операция подстановки в функцию от m переменных m функций от n переменных. (одних и тех же).
Пример. Функция f(x1,…, xn) возникает из функций h(x1,…, xm), g1(x1,…, xn), …gm(x1,…, xn) суперпозицией, если
f(x1,…, xn)= Snm(h, g1,…, gm) = h(g1(x1,…, xn), …, gm (x1,…, xn)).
Если заданы функции Jnm и операторы Snm, то можно считать заданными всевозможные операторы подстановки функции в функцию, а также переименования, перестановки и отождествления переменных.
Так, если f(x1, x2)= h(g1(x1, x2), g2(x1)), то ее стандартный вид следующий: f(x1, x2)= S22(h(x1, x2), g1 (x1, x2), S12 (J21(x1, x2), g2(x1), g3(x1))), где g3 – любая функция от х1. Если же имеем f(x2, x1, х3, …, xn) и f(x1, x1, x3,…, xn), то пишем:
f(x2, x1, х3, …, xn) = f(J22(x1, x2), J21(x1, x2), х3, …, xn),
f(x1, x1, x3,…, xn)= f(J21(x1, x2), J21(x1, x2), х3, …, xn).
Def. Оператором примитивной рекурсии Rn называется процесс определения функфии f (n+1) переменных через n-местную функцию g и (n+2)- местную функцию h в следующем виде:
f(x1, x2, …, xn, 0)= g(x1, x2,…, xn)
f(x1, x2, …, xn, y+1)=h(x1, x2,…, xn, y, f(x1, x2, …, xn, y)),
где g и h – две различные функции соответственно n и n+2 аргументов.
Эта пара равенств называется схемой примитивной рекурсии. Тот факт, что функция f определена схемой примитивной рекурсии выражается равенством f(x1, x2, …, xn, y)=Rn(g, h). В случае, когда n=0, то есть определяемая функция f является одноместной, схема примитивной рекурсии принимает более простой вид:
f(0)=с, f(у+1)=h(y, f(y)), где с – константа.
Схема
примитивной рекурсии определяет f
рекурсивно не только через другие
функции g
и h,
но и через значения f в предшествующих
точках: значение функции f в точке у+1
зависит от значения функции f в точке
у. Очевидно, что для вычисления f(x1,…,
xn,
k)
понадобиться k+1
вычислений по схеме примитивной рекурсии
– для у=0, k.
Замечания:
Существенным в операторе примитивной рекурсии Rn является то, что независимо от числа переменных в f рекурсия ведется только по одной переменной у (остальные n переменных x1, x2, …, xn на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров).
Формальное индуктивное определение примитивно-рекурсивной функции следующее:
функции 0, х`, Jnm для всех натуральных n, m, где nm являются примитивно-рекурсивными;
если g1(x1,…, xn), …gm(x1,…, xn), h(x1,…, xm) - примитивно-рекурсивные функции, то Snm(h, g1,…, gm) - примитивно-рекурсивные функции для любых натуральных n, m;
если g(x1,…, xn) и h(x1,…, xm, у, z) - примитивно-рекурсивные функции, то Rn(g, h) – примитивно-рекурсивная функция;
других примитивно-рекурсивных функций нет.
Схемной интерпретацией примитивной рекурсии может быть схема:
Эта схема состоит из элемента, вычисляющего за один такт функцию h от двух переменных и элемента задержки на один такт. По каналам схемы могут передаваться натуральные числа. Время t считается дискретным, то есть t=0, 1, 2, 3…. Схема имеет один вход х и один выход f. Выход f зависит не только от х, но и от момента t, в котором он рассматривается. В начальный момент t=0 второй вход h является константой с, зависящей от начального состояния схемы: f(x, 0)=h(x, c)=g(x). В момент t=1: f(x, 1)=h(x, f(x, 0)); в общем случае f(x, t+1)=h(x, f(x,t)). Нетрудно убедиться, например, что если h выполняет умножение, а с=1, то f(x, t)=xt+1.
Поскольку исходные (базисные) функции являются вычислимыми, а операторы суперпозиции и примитивной рекурсии вычислимость сохраняют, то множество всех примитивно-рекурсивных функций есть подкласс класса всех вычислимых функций;
Класс всех примитивно-рекурсивных функций счетен, поскольку каждая такая функция задается описанием ее построения из исходных функций.
Практически все арифметические функции, употребляемые в математике по конкретным поводам, являются примитивно-рекурсивными функциями, например: х+у, х*у, ху и т.д.