SHPORA.net :: PDA

[ Back ]

2.3 Рекурсивные функции

Каждый алгоритм однозначно ставит в соответствие исходным данным результат. Следовательно, с каждым алгоритмом однозначно связана некая функция, которую он вычисляет. На выяснении вопроса для каких функций алгоритмы существуют, а для каких нет основана теория рекурсивных функций.
Основным в ней является то, что все множество исследуемых функций строится из конечного числа исходных функций (базиса) с помощью простых операций, эффективная выполнимость которых достаточно очевидна. Операции над функциями будем называть операторами.

2.3.1 Примитивно ? рекурсивные функции
К вычислимым функциям можно отнести все константы, т.е. 0 и все натуральные числа 1,2,?. Но можно обойтись 0 и функцией следования f(x)=x+1(x'). Кроме того в базис включим функции тождества, обозначим семейство таких функций {Inm}: Inm(x1,x2,..,xn)=xm(m≤n). Иначе ее можно назвать функцией введения фиктивных переменных. Определим семейство операторов суперпозиции {Snm} : для h(x1,?,xm), gi(x1,?,xn), i=1,?,m.
Snm (h,g1,?gm)=h(g1(x1,?,xn),?, gm (x1,?,xn))=f(x1,?,xn).
Оператор примитивной рекурсии Rn
определяет (n+1)-местную функцию f через n-местную функцию g и (n+2)-местную функцию h таким образом:

f(x1,?,xn,0)= g(x1,?,xn)
f(x1,?,xn,y+1)= h(x1,?,xn,y, f(x1,?,xn,y))

Эти формулы называются схемой примитивной рекурсии.
В случае, когда f одноместна, получаем следующее представление схемы
f(0)=c
f(y+1)=h(y,f(y))
Для вычисления f(x1,?,xn,k) понадобится (k+1) вычислений по схеме при y=0,1,2,..,k.
Функция называется примитивно-рекурсивной, если она может быть получена из константы 0, функции x? и функций Inm с помощью применения конечного числа операторов суперпозиций и схем примитивной рекурсии.


Примеры

1. Сложение f+(x,y)=x+y - примитивно рекурсивно
f+(x,0)=x=I11(x)
f+(x,y+1)=f+(x,y)+1=(f+(x,y))'
2. Умножение f×(x,y)=xy - примитивно рекурсивно,
f×(x,0)=0
f×( x,y+1)= f×( x,y)+ x= f×( x, f×( x,y))
3. Возведение в степень fexp(x, y)=xy - примитивно рекурсивно
fexp(x, 0)=1
fexp(x, y+1)= xy x= f×( x, fexp(x, y))
Определим функцию x 0 y (арифметическое вычитание)
Покажем примитивную рекурсию следующих функций
4а) f(x)= x 1 определяется схемой:
f(0)=0  1=0
f(y+1)=y
4б) f(x,y)= x y
f(x,0)=x
f( x,y+1)=x  (y+1)=(x  y)  1= f(x,y)  1
4в) f(x,y) = |x-y|= (x  y)+(y  x)
4г)
sg(0)=0
sg(x+1)= 1
4д) min (x,y)=x  (x  y)
4е) max (x,y)= y+(x  y)

5а). r(x,y) ? остаток от деления y на x
например, r(3,5)=2), r(3,8)=2, r(x,0)=0
т.е. r(x,y+1)=(r(x,y)+1) sg(|x  (r(x,y)+1)|)
если y+1 не делится на x, то sg(|x  (r(x,y)+1)|)=1 и r(x,y+1)= r(x,y)+1
если y+1 делится на x, то r(x,y)+1= sg(|x  (r(x,y)+1)|)=0
5б). q(x,y)=[y/x] ? частное от деления y на x, т.е. целая часть дроби.
q(x,0)=0 (sg(x)=1  sg(x))
т.е. q( x,y+1)=q(x,y)+sq(|x(r(x,y)+1)|)
если y+1 делится на x , то q( x,y+1) на 1 больше, чем q(x,y).
если нет, то q( x,y+1)= q(x,y).
a mod b ? целый остаток
a div b ? целая часть b/a
Из этих примеров следует примитивная рекурсия ?арифметизированных? логических функций, т.е. функций числовых, которые на множестве {0,1} ведут себя как логические. Действительно, если х,у{0,1}, то

х = 1  х
x  y = max (x,y)
x  y = min (x,y)

т.к? {,,} полная система логических функций и суперпозиция ? примитивно-рекурсивный оператор, то все логические функции примитивно - рекурсивны.
Отношение R(x1,?,xn) называется примитивно-рекурсивным, если примитивно-рекурсивна его характеристическая функция R :

Предикат называется примитивно?рекурсивным, если его характеристическая функция примитивно?рекурсивна. В силу выражения логических функций через арифметические, если предикаты P1,?,Pn - примитивно?рекурсивны, то полученный из них с помощью логических операторов любой другой предикат - примитивно?рекурсивен.

Пример
1. P(n,x) : x делится на n
P(n,x) примитивно?рекурсивен, т.к. его характеристическая функция

2. P(n,m,x): x делится на m и на n
P(n,m,x): - примитивно?рекурсивен для любого m и n, т.к.
Pn,m(x)=Pm(x) Pn(x)


2.3.2 Примитивно ? рекурсивные операторы

Примитивно?рекурсивный оператор сохраняет примитивно-рекурсивные функции , то есть результат его применения к примитивно?рекурсивным функциям дает снова примитивно?рекурсивную функцию. Операторы Snm , Rn ? примитивно?рекурсивные операторы по определению. Рассмотрим другие примитивно?рекурсивные операторы. Их использование позволяет существенно сократить примитивно ? рекурсивное описание функций.
и ? примитивно?рекурсивные операторы (т.к. используют только и , примитивная рекурсия, котораых доказана). Такими операторами являются суммирование и умножение от k до z:
и
- оператором или ограниченным оператором наименьшего числа (или ограниченным оператором минимизации) называется


Из предиката P(x1,?,xn,y) с помощью оператора y≤z получается функция . Второй случай в определении добавлен для того, чтобы была всюду определена.

Пример

Рассмотрим предикат предыдущего примера
тогда



Ограниченный - оператор примитивно?рекурсивен, так как его характеристическая функция имеет вид



Ограничение z в ограниченном - операторе дает гарантию окончания вычислений, поскольку оно оценивает сверху число вычислений предиката P.
Далее будет показано, что неограниченный - оператор не является примитивно ? рекурсивным.

2.3.3 Частично ? рекурсивные функции

Не все функции примитивно?рекурсивные, так как каждая примитивно?рекурсивная функция имеет конечное описание, т.е. задается конечным словом в некотором алфавите. Множество конечных слов счетно, следовательно примитивно?рекурсивные функции образуют счетное подмножество несчетного множества функций типа . ( Например функция Аккермана - вычислима, но растет быстрее, чем любая примитивно?рекурсивная функция поэтому не является примитивно?рекурсивной).
Следовательно вычисляемые функции не обязательно примитивно?рекурсивные. Введем новое понятие рекурсивности функций:

Частично-рекурсивная функция ? это функция, которая может быть построена из простейших функций 0, x+1, Inm с помощью конечного числа применения суперпозиций, примитивной рекурсии и неограниченного оператора.
При этом - оператору можно придать стандартную форму:
f(x1,?,xn) = y(g(x1,?,xn-1,y)= xn) или
f(x1,?,xn) = y(g(x1,?,xn-1,y)= 0)
Таким образом, среди рекурсивных функций появляются не полностью определенные, т.е. частичные функции (когда g(x1,?,xn-1,y)=0 не имеет решения).


Общерекурсивная функция ? частично- рекурсивная функция, если она всюду определена. (Например, функция Аккермана).

Тезис Черча
Всякая функции, вычислимая некоторым оператором, частично?рекурсивна.

Теорема
Всякая функция вычислимая на машине Тьюринга ? частично ?рекурсивна.