Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Recur func (т. алгоритмов)

.pdf
Скачиваний:
12
Добавлен:
06.02.2015
Размер:
178.66 Кб
Скачать

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

Тезис Черча: класс интуитивно вычислимых функций совпадает с классом частично рекурсивных функций.

Определение 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.

Отсюда и из полноты системы {−, , } следует примитивная рекурсивность всех логических функций.

(sgn(χS((y + 1)2, x)) = 0),

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).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]