Ограниченный оператор минимизации

Определение 2.4. Функция f (x 1 ,..., xn) получается ограниченным оператором минимизации из предиката P (x 1 ,..., xn, z) и граничной функции U (x 1 ,..., xn), если в любой точке значение этой функции определяется следующим образом:

а) существует z < U (x 1, x 2 ,..., xn) такое, что P (x 1 ,..., xn, z) = "истина тогда

f (x 1 ,..., xn) = µz (P (x 1 ,..., xn, z));

б) не существует z < U (x 1 ,..., xn) такое, что P (x 1 ,..., xn, z) = "истина тогда в качестве значения функции принимается значение граничной функции:

 

f (x 1 ,..., xn) = U (x 1 ,..., xn)

 

.

Сразу заметим, что в определении (2.4) отношение z < U (x 1, x 2 ,..., xn) можно

было бы заменить на z ≤ U (x 1, x 2 ,..., xn) — значение функции не изменилось бы. С учетом эквивалентности таких определений иногда будем использовать второе из этих отношений, если это окажется удобным. Записывается определение функции f (x 1 ,..., xn), полученной с помощью ограниченного оператора минимизации, как

 

f (x 1 ,..., xn) = µz<U (x 1 ,...,xn)(P (x 1 ,..., xn, z)). (2. 4)

 

Ясно, что алгоритм вычисления функции (2.4) получен из алгоритма вычисления (2.3) дополнением условия так, чтобы имелась гарантия завершения цикла:

 

int f(int x1,..., int xn)

{

int z=0;

while (!P(x1,..., xn,z) && (z<U(x1,...,xn)) z++; return z;

}

 

Докажем, что ограниченный оператор минимизации является примитивно–рекур- сивным. Рассмотрим сначала вспомогательные утверждения.

Теорема 2.2. Функция

 

y

g (x 1 ,..., xn, y) = ∑ f (x 1 ,..., xn, i)

i =0

 

является примитивно–рекурсивной при условии примитивной рекурсивности функ- ции f (x 1 ,..., xn, i).

Доказательство. Представим g (x 1 ,..., xn, y) с помощью схемы примитивной ре- курсии от примитивно–рекурсивных функций:

 

g (x 1 ,..., xn, 0) = ∑ f (x 1 ,..., xn, i) = f (x 1 ,..., xn, 0)

i =0

y +1

g (x 1 ,..., xn, y + 1) = ∑ f (x 1 ,..., xn, i) =

i =0

= g (x 1 ,..., xn, y) + f (x 1 ,..., xn, y + 1).

Q

Теорема 2.3. Функция

 

y

g (x 1 ,..., xn, z, y) = ∑ f (x 1 ,..., xn, i)

i = z

является примитивно–рекурсивной, если функция f (x 1 ,..., xn, i) примитивно–рекур- сивна.

Доказательство. Запишем функцию g (x 1 ,..., xn, z, y) в виде суперпозиции при- митивно–рекурсивных функций:

g (x 1 ,..., xn, z, y) =

(y

= ∑ f (x 1 ,..., xn, i)−˙

i =0

z)

∑ f (x 1 ,..., xn, i) + f (x 1 ,..., xn, z)

i =0

· χ (z ≤ y).

Здесь χ (z ≤ y) —характеристическая функция предиката (z ≤ y), которая является примитивно–рекурсивной, т.к. может быть представлена в виде суперпозиции прими- тивно – рекурсивных функций сложения, усеченной разности и знаковой функции: χ (z ≤ y) = sg (y + 1−˙ z). Q

Теорема 2.4. Функция

 

 

g (x 1 ,..., xn) =

U (x 1 ,...,xn)

∑

 

i = V (x 1 ,...,xn)

 

f (x 1 ,..., xn, i)

 

является примитивно–рекурсивной, если примитивно–рекурсивны функции

U (x 1 ,..., xn), f (x 1 ,..., xn, i), V (x 1 ,..., xn).

Доказательство очевидно, т.к. функция g (x 1 ,..., xn) является суперпозицией за- данных примитивно–рекурсивних функций и функции, примитивно–рекурсивной по теореме 2.3. Q

Аналогичные теоремы можно доказать для произведения.

Теорема 2.5. Функция

 

y

g (x 1 ,..., xn, y) = ∏ f (x 1 ,..., xn, i)

i =0

 

является примитивно–рекурсивной, если функция f (x 1 ,..., xn, i) примитивно–рекур- сивна.

Теорема 2.6. Функция

 

y

g (x 1 ,..., xn, z, y) = ∏ f (x 1 ,..., xn, i)

i = z

является примитивно–рекурсивной, если примитивно–рекурсивна f (x 1 ,..., xn, i).

Теорема 2.7. Функция

 

 

g (x 1 ,..., xn) =

U (x 1 ,...,xn)

∏

 

i = V (x 1 ,...,xn)

 

f (x 1 ,..., xn, i)

 

является примитивно–рекурсивной, если примитивно–рекурсивны функции

U (x 1 ,..., xn), f (x 1 ,..., xn, i), V (x 1 ,..., xn).

Теорема 2.8. Функция

 

g (x 1 ,..., xn) = µz<U (x 1 ,x 2 ,...xn)(P (x 1 ,..., xn, z)),

построенная с помощью ограниченного оператора минимизации из примитивно–ре- курсивного предиката P (x 1 ,..., xn, z) и примитивно–рекурсивной функции U (x 1 ,..., xn), является примитивно–рекурсивной.

Доказательство. Представим функцию g (x 1 ,..., xn) в виде вспомогательной примитивно–рекурсивной функции и покажем, что в любой точке эти функции рав- ны.

Рассмотрим функцию

 

U (x 1 ,...,xn) − ˙1 (i)

g ˜(x 1 ,..., xn) =

∑

 

i =0

∏(1−˙ χp (x 1 ,..., xn, j))

j =0

. (2. 5)

В соответствии с определением функции g (x 1 ,..., xn) рассмотрим два случая вы- числения функции g ˜(x 1 ,..., xn).

Первый вариант вычисления (2.5) соответствует случаю, когда не существует z < U (x 1 ,..., xn), такое, что χp (x 1 ,..., xn, z) = 1. Тогда для любого z < U (x 1 ,..., xn)

имеем (1−˙ χp (x 1 ,..., xn) z)= 1, отсюда для любого i < U (x 1 ,..., xn)

(1−˙ χp (x 1 ,..., xn, z))= 1,

 

 

следовательно, в соответствии с (2.5)

 

U (x 1 ,...,xn) − ˙1 (i)

∑

 

i =0

∏(1−˙ χp (x 1 ,..., xn, j)

j =0

= U (x 1 ,..., xn).

Функция g (x 1 ,..., xn) по определению в этом случае также равна U (x 1 ,..., xn).

Рассмотрим второй вариант вычисления функции (2.5): пусть найдется такое z < U ((x 1 ,..., xn), что χp (x 1 ,..., xn, z) = 1, тогда

1−˙ χp (x 1 ,..., xn, 0) = 1,

1−˙ χp (x 1 ,..., xn, 1) = 1,

...

1−˙ χp (x 1 ,..., xn, z − 1) = 1,

1−˙ χp (x 1 ,..., xn, z) = 0.

Следовательно

 

∏(1−˙ χp (x 1 ,..., xn, j))= 1,

j =0

...

z− 1

∏(1−˙ χp (x 1 ,..., xn, j))= 1,

j =0

z

∏(1−˙ χp (x 1 ,..., xn, j))= 0,

j =0

z +1

∏(1−˙ χp (x 1 ,..., xn, j))= 0,

j =0

...

Тогда сумма (2.5) равна z и в соответствии с определением ограниченного µ – опера- тора значение g (x 1 ,..., xn) также равно z. Таким образом, в любом случае g (x 1 ,..., xn) можно представить выражением (2.5): функции g ˜(x 1 ,..., xn) и g (x 1 ,..., xn) эквива- лентны. Но функция g ˜(x 1 ,..., xn) является суперпозицией примитивно–рекурсивных функций, следовательно, она примитивно–рекурсивна, а, значит, примитивно–рекур- сивна и функция g (x 1 ,..., xn). Q

Пример. Показать, что функция [ x/ (y + 1)] является примитивно–рекурсивной. Очевидно, что [ x/ (y + 1)] = µz<x +1 ([ x/ (y + 1)] = z). Рассмотрим два случая.

Пусть x нацело делится на y + 1, тогда

 

[ x/ (y + 1)] = µz<x +1 (x = z (y + 1)).

Пусть x нацело не делится на y + 1, тогда в соответствии с определением ограни- ченного оператора минимизации подставляя в качестве z значения 0,1,2,.. в преди- кат x = z (y + 1) будем получать неравенство x > z (y + 1) до тех пор, пока зна- чение z не достигнет [ x/ (y + 1)]. Тогда при подстановке значения z + 1 получим отношение x < (z + 1) · (y + 1). Объединяя оба варианта, получим [ x/ (y + 1)] =

µz<x +1 (x < (z + 1) · (y + 1)). Характеристическая функция sg ((z + 1) · (y + 1)−˙ x)

предиката и граница s (x) — примитивно – рекурсивные функции, тогда и [ x/ (y + 1)]

примитивно–рекурсивна.

Пример. Показать, что τ (x) — число делителей числа x — является примитив-

но–рекурсивной функцией.

x

Очевидно, что τ (x) = ∑ sg { x/i }. Выполняя подстановку для i = y + 1, получим

i =1

τ (x) =

x− ˙1

∑ sg { x/ (y + 1)}. Остаток от деления { x/ (y + 1)} равен x −˙[ x/ (y + 1)]. Тогда

y =0

τ (x) является суперпозицией примитивно–рекурсивных функций.

Таким образом, ограниченным оператором минимизации можно пользоваться при построении примитивно–рекурсивных функций. Возникает вопрос: достаточно ли класса примитивно–рекурсивных функций для построения определения любого ал- горитма. Чтобы показать недостаточную порождающую силу данного класса функ- ций, необходимо привести пример функции, для которой существует алгоритм ее вычисления, но которая не является примитивно–рекурсивной. Этим мы и займемся в следующем параграфе.