Ограниченный оператор минимизации
Определение 2.4.Функция f (x1, . . . , xn) получается ограниченным оператором минимизации из предиката P (x1, . . . , xn, z) и граничной функции U (x1, . . . , xn), если в любой точке значение этой функции определяется следующим образом:
а) существует z < U (x1, x2, . . . , xn) такое, что P (x1, . . . , xn, z) = "истина тогда
f (x1, . . . , xn) = µz (P (x1, . . . , xn, z)) ;
б) не существует z < U (x1, . . . , xn) такое, что P (x1, . . . , xn, z) = "истина тогда в качестве значения функции принимается значение граничной функции:
f (x1, . . . , xn) = U (x1, . . . , xn)
.
Сразу заметим, что в определении (2.4) отношение z < U (x1, x2, . . . , xn) можно
было бы заменить на z ≤ U (x1, x2, . . . , xn) — значение функции не изменилось бы. С учетом эквивалентности таких определений иногда будем использовать второе из этих отношений, если это окажется удобным. Записывается определение функции f (x1, . . . , xn), полученной с помощью ограниченного оператора минимизации, как
f (x1, . . . , xn) = µz<U(x1,...,xn)(P (x1, . . . , 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(x1, . . . , xn, y) = ∑ f (x1, . . . , xn, i)
i=0
является примитивно–рекурсивной при условии примитивной рекурсивности функ- ции f (x1, . . . , xn, i).
Доказательство.Представим g(x1, . . . , xn, y) с помощью схемы примитивной ре- курсии от примитивно–рекурсивных функций:
g(x1, . . . , xn, 0) = ∑ f (x1, . . . , xn, i) = f (x1, . . . , xn, 0)
i=0
y+1
g(x1, . . . , xn, y + 1) = ∑ f (x1, . . . , xn, i) =
i=0
= g(x1, . . . , xn, y) + f (x1, . . . , xn, y + 1).
Q
Теорема 2.3.Функция
y
g(x1, . . . , xn, z, y) = ∑ f (x1, . . . , xn, i)
i=z
является примитивно–рекурсивной, если функция f (x1, . . . , xn, i) примитивно–рекур- сивна.
Доказательство.Запишем функцию g(x1, . . . , xn, z, y) в виде суперпозиции при- митивно–рекурсивных функций:
g(x1, . . . , xn, z, y) =
( y
= ∑f (x1, . . . , xn, i)−˙
i=0
z )
∑ f (x1, . . . , xn, i) + f (x1, . . . , xn, z)
i=0
· χ(z ≤ y).
Здесь χ(z ≤ y) —характеристическая функция предиката (z ≤ y), которая является примитивно–рекурсивной, т.к. может быть представлена в виде суперпозиции прими- тивно – рекурсивных функций сложения, усеченной разности и знаковой функции: χ(z ≤ y) = sg(y + 1−˙z) . Q
Теорема 2.4.Функция
g(x1, . . . , xn) =
U (x1,...,xn)
∑
i=V (x1,...,xn)
f (x1, . . . , xn, i)
является примитивно–рекурсивной, если примитивно–рекурсивны функции
U (x1, . . . , xn), f (x1, . . . , xn, i), V (x1, . . . , xn).
Доказательство очевидно, т.к. функция g(x1, . . . , xn) является суперпозицией за- данных примитивно–рекурсивних функций и функции, примитивно–рекурсивной по теореме 2.3. Q
Аналогичные теоремы можно доказать для произведения.
Теорема 2.5.Функция
y
g(x1, . . . , xn, y) = ∏ f (x1, . . . , xn, i)
i=0
является примитивно–рекурсивной, если функция f (x1, . . . , xn, i) примитивно–рекур- сивна.
Теорема 2.6.Функция
y
g(x1, . . . , xn, z, y) = ∏ f (x1, . . . , xn, i)
i=z
является примитивно–рекурсивной, если примитивно–рекурсивна f (x1, . . . , xn, i).
Теорема 2.7.Функция
g(x1, . . . , xn) =
U (x1,...,xn)
∏
i=V (x1,...,xn)
f (x1, . . . , xn, i)
является примитивно–рекурсивной, если примитивно–рекурсивны функции
U (x1, . . . , xn), f (x1, . . . , xn, i), V (x1, . . . , xn).
Теорема 2.8.Функция
g(x1, . . . , xn) = µz<U (x1,x2,...xn)(P (x1, . . . , xn, z)),
построенная с помощью ограниченного оператора минимизации из примитивно–ре- курсивного предиката P (x1, . . . , xn, z) и примитивно–рекурсивной функции U (x1, . . . , xn), является примитивно–рекурсивной.
Доказательство.Представим функцию g(x1, . . . , xn) в виде вспомогательной примитивно–рекурсивной функции и покажем, что в любой точке эти функции рав- ны.
Рассмотрим функцию
U (x1,...,xn)−˙1 (i )
g˜(x1, . . . , xn) =
∑
i=0
∏(1−˙χp(x1, . . . , xn, j))
j=0
. (2.5)
В соответствии с определением функции g(x1, . . . , xn) рассмотрим два случая вы- числения функции g˜(x1, . . . , xn).
Первый вариант вычисления (2.5) соответствует случаю, когда не существует z < U (x1, . . . , xn), такое, что χp(x1, . . . , xn, z) = 1. Тогда для любого z < U (x1, . . . , xn)
имеем (1−˙χp(x1, . . . , xn)z)= 1, отсюда для любого i < U (x1, . . . , xn)
(1−˙χp(x1, . . . , xn, z))= 1,
следовательно, в соответствии с (2.5)
U (x1,...,xn)−˙1 (i )
∑
i=0
∏(1−˙χp(x1, . . . , xn, j)
j=0
= U (x1, . . . , xn).
Функция g(x1, . . . , xn) по определению в этом случае также равна U (x1, . . . , xn).
Рассмотрим второй вариант вычисления функции (2.5): пусть найдется такое z < U ((x1, . . . , xn), что χp(x1, . . . , xn, z) = 1, тогда
1−˙χp(x1, . . . , xn, 0) = 1,
1−˙χp(x1, . . . , xn, 1) = 1,
. . .
1−˙χp(x1, . . . , xn, z − 1) = 1,
1−˙χp(x1, . . . , xn, z) = 0.
Следовательно
∏(1−˙χp(x1, . . . , xn, j))= 1,
j=0
. . .
z−1
∏(1−˙χp(x1, . . . , xn, j))= 1,
j=0
z
∏(1−˙χp(x1, . . . , xn, j))= 0,
j=0
z+1
∏(1−˙χp(x1, . . . , xn, j))= 0,
j=0
. . .
Тогда сумма (2.5) равна z и в соответствии с определением ограниченного µ – опера- тора значение g(x1, . . . , xn) также равно z. Таким образом, в любом случае g(x1, . . . , xn) можно представить выражением (2.5): функции g˜(x1, . . . , xn) и g(x1, . . . , xn) эквива- лентны. Но функция g˜(x1, . . . , xn) является суперпозицией примитивно–рекурсивных функций, следовательно, она примитивно–рекурсивна, а, значит, примитивно–рекур- сивна и функция g(x1, . . . , 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) является суперпозицией примитивно–рекурсивных функций.
Таким образом, ограниченным оператором минимизации можно пользоваться при построении примитивно–рекурсивных функций. Возникает вопрос: достаточно ли класса примитивно–рекурсивных функций для построения определения любого ал- горитма. Чтобы показать недостаточную порождающую силу данного класса функ- ций, необходимо привести пример функции, для которой существует алгоритм ее вычисления, но которая не является примитивно–рекурсивной. Этим мы и займемся в следующем параграфе.