Recur func (т. алгоритмов)
.pdfРекурсивные функции
Тезис Черча: класс интуитивно вычислимых функций совпадает с классом частично рекурсивных функций.
Определение 1. Следующие функции называются исходными:
1)нуль-функция: Z(x) = 0 для любого x N;
2)функция следования: N(x) = x + 1 для любого x N;
3)проектирующие функции: Uin(x1, ..., xn) = xi для всех x1, ..., xn N (i = 1, ..., n, n N);
4)константа: нульместная функция Ca, принимающая постоянное значение a.
Определение 2. Правила образования новых функций из уже имеющихся:
1) Говорят, что функция f(x1, ..., xn) получена подстановкой из функций g(y1, ..., ym), h1(x1, ..., xn),...,hm(x1, ..., xn), если
f(x1, ..., xn) = g(h1(x1, ..., xn), ..., hm(x1, ..., xn)).
2) Говорят, что n-местная функция f получена из (n − 1)-местной функции g и (n + 1)- местной функции h с помощью рекурсии, если
f(x1, ..., xn−1, 0) = g(x1, ..., xn−1),
f(x1, ..., xn−1, y + 1) = h(x1, ..., xn−1, y, f(x1, ..., xn−1, y)).
В частности, при n = 1 имеем:
f(0) = const,
f(y + 1) = h(y, f(y)).
3) Говорят, что функция f(x1, .., xn) получена из функции g(x1, .., xn, y) с помощью µ- оператора (оператора минимизации), если выполнено условие: f(x1, .., xn) определено и равно y тогда и только тогда, когда g(x1, .., xn, 0), .., g(x1, .., xn, y−1) определены и не равны 0, а g(x1, .., xn, y) = 0. Обозначение:
f(x1, .., xn) = µy(g(x1, .., xn, y) = 0).
Замечание 1. Функция f, полученная из функции g применением µ-оператора, не определена в точке (x01, x02, .., x0n) в одном из следующих случаев:
-если не существует такого значения y, что g(x01, .., x0n, y) = 0;
-если для i = 0, .., t − 1 значения g(x01, .., x0n, i) не равны 0, а значение g(x01, .., x0n, t) не определено (при этом возможно, что g(x01, .., x0n, y) = 0 для некоторого y > t).
Определение 3. Функция f называется частично рекурсивной, если она может быть получена из исходных функций с помощью конечного числа применений правил подстановки, рекурсии и µ-оператора.
Если частично рекурсивная функция f может быть получена без применения µ- оператора, то она называется примитивно-рекурсивной.
Упражнение 1. Доказать, что всякая примитивно-рекурсивная функция всюду определена.
Определение 4. Частично рекурсивная функция f называется общерекурсивной (или рекурсивной), если она всюду определена.
Замечание 2. Не всякая рекурсивная функция примитивно рекурсивна. Одно из доказательств данного факта основывается на том, что всякая примитивно-рекурсивная функция достаточно медленно растет и можно предъявить рекурсивную функцию, растущую
1
2
быстрее всех примитивно-рекурсивных. Примерами таких функций служат функции Аккермана.
Докажем, что введение фиктивных переменных, перестановка и отождествление переменных не выводят из класса частично рекурсивных функций, т.е. что верно
Предложение 1. Если функция g(y1, ..., yk) частично рекурсивна и x1, ..., xn – различные переменные, причем при любом i, 1 ≤ i ≤ k, zi есть одна из переменных x1, ..., xn, то функция
f(x1, ..., xn) = g(z1, ..., zk)
также частично рекурсивна.
|
|
|
|
n |
(x1, ..., xn) и f(x1, ..., xn) = |
||
Доказательство. Пусть zi = xji (1 ≤ j ≤ n). Тогда zi = Uji |
|||||||
|
n |
n |
|
|
n |
n |
C |
g Uj1 |
(x1, ..., xn), ..., Ujk |
(x1, ..., xn) , т.е. f |
получается из функций g, Uj1 |
, ..., Ujk |
подстанов- |
кой, а, значит, частично рекурсивна, т.к. эти функции частично рекурсивны.
Замечание 3. Нетрудно видеть, что если в предложении 1 функция g примитивнорекурсивна, то и f примитивно-рекурсивна.
Из предложения 1 получаем такое следствие.
Предложение 2.
а) Нуль-функция Zn(x1, ..., xn) = 0 примитивно-рекурсивна.
б) Постоянная функция Ckn(x1, ..., xn) = k примитивно-рекурсивна.
в) Правило подставновки может быть распространено и на случай, когда функции hi являются функциями лишь от некоторых из переменных x1, ..., xn. Аналогично, правило рекурсии распространяется и на случаи, когда функция g не зависит от некоторых из переменных x1, ..., xn−1, а функция h может не зависеть от некоторых из переменных x1, ..., xn+1.
Доказательство. а) Если в предложении 1 положить g(x) = Z(x), k = 1, z1 = x1, то
получим Zn(x1, ..., xn) = Z(x1), а, значит, Zn примитивно-рекурсивна. |
|
б) Доказывается индукцией по k. Заметим, что при k = 0 имеем: Cn(x1, ..., xn) |
= |
0 |
|
Zn(x1, ..., xn), т.е. C0n примитивно-рекурсивна. |
|
Шаг индукции: Ckn+1(x1, ..., xn) = N (Ckn(x1, ..., xn)) . |
|
в) Следует сразу из возможности введения фиктивных переменных. |
C |
Примеры примитивно-рекурсивных функций
Предложение 3. Следующие функции являются примитивно-рекурсивными:
1) s(x, y) = x + y; |
|
||||
2) p(x, y) = x · y; |
если x = y = 0; |
||||
3) |
Φ(x, y) = |
|
1, |
||
|
δ(x) = |
|
xy, |
если x > 0 или y > 0, |
|
4) |
0,− |
1, |
если x = 0; |
||
|
|
x |
|
если x > 0, |
5) x |
− |
|
|
|
0,− |
y, |
если x < y; |
|||
. |
y = |
|
x |
если x ≥ y, |
||||||
|
| |
|
− |
|
| |
|
y − x, |
если x < y; |
||
6) |
|
x |
|
y |
|
= |
|
x − y, |
если x ≥ y, |
3
7) sgn(x) =
0, если x = 0,
1, если x > 0;
8) sgn(x) =
1, если x = 0,
0, если x > 0;
9)x!;
10)min(x, y);
11)min(x1, ..., xn);
12)max(x, y);
13)max(x1, ..., xn);
|
|
|
|
остаток от деления x на y, если y > 0, |
|
14) r(x, y) = x, |
если y = 0; |
||||
|
y |
= |
|
частное от деления y на x, |
если x > 0, |
15) |
x |
y, |
если x = 0; |
Доказательство.
1) Имеем:
s(x, 0) = x = U11(x) =: g(x),
s(x, y + 1) = N(s(x, y)) = N(U33(x, y, s(x, y))) =: h(x, y, s(x, y)).
Таким образом, функция s(x, y) получается из примитивно-рекурсивных функций g (одноместной) и h (трехместной) по правилу рекурсии, а значит, является примитивнорекурсивной (заметим, что h получена подстановкой из исходных функций N(x) и
U33(x1, x2, x3)).
2) p(x, 0) = Z(x) =: g(x),
p(x, y + 1) = s(p(x, y), x) = s(U13(x, y, p(x, y)), U33(x, y, p(x, y))) =: h(x, y, p(x, y)).
3) Функция Φ(x, y) = xy определяется с помощью рекурсии следующим образом:
Φ(x, 0) = x0 = 1 = C11(x),
Φ(x, y + 1) = xy+1 = x · (xy) = p(x, Φ(x, y)) = p(U13(x, y, Φ(x, y), U33(x, y, Φ(x, y))).
4) δ(0) = 0 = Z(x),
δ(y + 1) = y = U12(y, δ(y)).
.
5) x − 0 = x = U11(x),
. |
. |
|
. |
|
x − (y + 1) = δ(x − y) = U33 |
(x, y, δ(x − y)). |
|
||
|
. |
. |
. |
. |
6) |x − y| = (x − y) + (y − x) = s(x − y, y − x), т.е. функция |x − y| получается с помощью правила подстановки из примитивно-рекурсивных функций, а значит, |x − y| примитивно-рекурсивна.
7) |
sgn(0) = 0 |
= C0, sgn(y + 1) = 1 = C2 |
(y, sgn(y)). |
|||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
. |
. |
|
|
|
8) |
|
|
x) = |
1 − sgn(x) = C1 |
− .sgn(x), т.е. |
|
x) получается подстановкой из |
|
|
sgn( |
sgn( |
примитивно-рекурсивных функций C1, − и sgn(x), а значит, она примитивно-рекурсивна.
9) 0! = 1 = C1,
(y + 1)! = y! · (y + 1) = p(y!, y + 1) = p(N(y), y!).
..
10) min(x, y) = x − (x − y), т.е. функция min(x, y) получается подстановкой из примитивно-рекурсивных функций.
4
11) Доказывается методом |
математической индукции: min(x1, ..., xn+1) |
= |
min(min(x1, ..., xn), xn+1). |
|
|
. |
. |
|
12) max(x, y) = y + (x − y) = s(y, x − y).
13) max(x1, ..., xn+1) = max(max(x1, ..., xn), xn+1).
14) r(0, y) = Z(y),
r(x + 1, y) = N(r(x, y)) · sgn(|y − N(r(x, y))|).
15) |
0 |
= Z(y), |
|
|
|
|
|
|
|
||
x+1 y |
x |
|
|
|
|
|
|
|
|
C |
|
+ sgn(|y − N(r(x, y))|). |
|
||||||||||
y |
= |
y |
|
||||||||
Упражнение 2 |
. Пусть функция |
g(x1, .., xn) |
примитивно-рекурсивна. Доказать, что сле- |
||||||||
|
|
|
|
|
|
||||||
дующие функции примитивно-рекурсивны: |
|
|
|||||||||
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
iP |
|
|
|
|
|
а) f(x1, .., xn−1, y) = |
g(x1, .., xn−1, i); |
|
|
||||||||
|
|
|
|
|
=0 |
|
|
|
|
||
|
|
|
|
|
|
|
z |
|
если |
|
|
|
|
|
|
|
|
|
P |
|
|
||
б) f(x1, .., xn−1, y, z) = |
|
i=yg(x1, .., xn−1, i), |
если y ≤ z, |
||||||||
|
|
|
|
|
|
y |
0, |
|
|
y > z; |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
iQ |
|
|
|
|
|
в) f(x1, .., xn−1, y) = |
g(x1, .., xn−1, i); |
|
|
||||||||
|
|
|
|
|
=0 |
|
|
|
|
||
|
|
|
|
|
|
|
z |
|
если |
|
|
|
|
|
|
|
|
|
Q |
|
|
||
г) f(x1, .., xn−1, y, z) = |
|
i=yg(x1, .., xn−1, i), |
если y ≤ z, |
||||||||
|
|
|
|
|
|
|
0, |
|
|
y > z. |
|
|
|
|
|
|
|
|
|
|
|
|
Ограниченный µ-оператор. Примитивно-рекурсивные предикаты
Определение 5. Говорят, что функция f(x1, .., xn) получена из функций g(x1, ..xn, xn+1) и h(x1, .., xn) с помощью ограниченного µ-оператора, если µy(g(x1, ..xn, y) = 0) определено для всех x1, .., xn и не больше h(x1, .., xn) и
f(x1, .., xn) = µy(g(x1, ..xn, y) = 0).
Будем использовать обозначение
f(x1, .., xn) = µyy≤h(x1,..,xn)(g(x1, ..xn, y) = 0).
Предложение 4. Если функция f получена из примитивно-рекурсивных функций g и h с помощью ограниченного µ-оператора, то f примитивно-рекурсивна.
h(x1,..,xn) i
P |
Q |
|
C |
Доказательство. f(x1, .., xn) = |
sgn |
g(x1, .., xn, j) . |
|
i=0 |
j=0 |
|
|
Рассмотрим теперь "арифметизированные" |
логические функции, т.е. функции f |
: |
{0, 1}n → {0, 1}. Нетрудно видеть, что
x y = min{x, y},
x y = max{x, y},
.
x = 1 − x.
Отсюда и из полноты системы {−, , } следует примитивная рекурсивность всех логических функций.
5
Определение 6. Предикат P (x1, .., xn) назовем примитивно-рекурсивным, если его характеристическая функция
χP (x1, .., xn) = |
0, |
если P (x1 |
, .., xn) = Л |
|
1, |
если P (x1 |
, .., xn) = И, |
примитивно-рекурсивна.
Из сказанного выше следует, что если предикаты P1, .., Pk примитивно-рекурсивны, то и любой предикат, полученный из них с помощью логических операций, примитивнорекурсивен.
Примеры.
а) Предикат P (x, y) ="x = y" примитивно-рекурсивен, так как χP (x, y) = sgn|x − y|.
б) Предикат Q(x, y) ="x делится на y" примитивно-рекурсивен, так как χQ(x, y) = sgn(r(x, y)).
в) Предикат R(x, y, z) ="x делится на y |
и на z" примитивно-рекурсивен, так как |
R(x, y, z) = Q(x, y) Q(x, z). |
. |
г) Предикат S(x, y) = ”x > y” примитивно-рекурсивен, так как χS(x, y) = sgn(x − y).
Применение µ-оператора и ограниченного µ-оператора
µ-оператор служит удобным инструментом построения обратных функций. Кроме того, не всюду определенные функции можно построить только с помощью µ-оператора.
Примеры.
√
а) Рассмотрим функцию [ x]. Чтобы доказать, что эта функция примитивнорекурсивна, покажем, что она получается из примитивно-рекурсивных функций с помо-
щью ограниченного µ-оператора. Действительно,
√
[ x] = µyy≤x
где S(x, y) – предикат из примера г). В таких случаях мы будем использовать запись
√
[ x] = µyy≤x((y + 1)2 > x).
б) [lg x] = µyy≤x(10y+1 > x), следовательно, функция [lg x] примитивно-рекурсивна. в) Рассмотрим частично рекурсивную функцию
f(x, y) = µz(|x − (z + y)| = 0).
Эта функция определена на таких наборах (x0, y0), что x0 ≥ y0. Действительно, если x0 ≥ y0, то существует (причем только одно) такое значение z0, что x0 = z0 + y0, а значит, |x0 − (z0 + y0)| = 0. При этом для i < z0 значения |x0 − (i + y0)| определены и не равны нулю. Если же x0 < y0, то не существует такого z0, что |x0 − (z0 + y0)| = 0. Таким образом, f(x, y) = x − y.
г) Функцию f(x) = µy(y − (x + 1) = 0) является частично рекурсивной. Покажем, что она нигде не определена. Пусть x = x0. Тогда при y0 = x0 + 1 получаем y0 −(x0 + 1) = 0, но при i < y0 значение i − (x0 + 1) не определено. По определению µ-оператора это означает, что функция µy(y − (x + 1) = 0) не определена в точке x0.
д) Функция |
xy , если y делит x, |
|
g(x, y) = |
||
не определена в противном случае |
||
частично рекурсивна, так как |
|
g(x, y) = µz(|x − z · y| = 0).