11.3. Примитивно рекурсивные множества

Будем называть множество примитивно рекурсив­ным, если его характеристическая функция примитивно рекурсивна. (Вариант: если оно является множеством ну­лей примитивно рекурсивной функции; это то же самое, так как можно сделать подстановку в функцию х >—>■ н->- 1 — х.)

Пересечение и объединение примитивно рекурсивных множеств примитивно рекурсивны (сложим или перем­ножим функции, множествами нулей которых они явля­ются) . Дополнение примитивно рекурсивного множества примитивно рекурсивно. Отождествляя множества со свойствами, можно сказать, что конъюнкции, дизъюнк­ции и отрицания примитивно рекурсивных свойств будут примитивно рекурсивны.

Свойства х = у и х ф у примитивно рекурсивны (х = = у тогда и только тогда, когда (х — у) + (у — х) = 0).

Функция f(x), заданная соотношением

f(x) = [ if R(x) then g(x) else h(x) fi ]будет примитивно рекурсивной, если таковы функции д и h и свойство R. В самом деле, f(x) можно записать как г(х)д(х) + (1 — r(x))h(x), где г — характеристическая функция свойства R.

Теперь можно записать формулу для прибавления еди­ницы по модулю п (для чисел, меньших п):

х + 1 mod п = [if х + 1 = п then 0 else х + 1 fi ]

После этого функцию х mod п (остаток от деления на п) можно определить рекурсивно:

О mod п + 1) mod п 0;

mod п) + 1 mod п.

Покажем, что ограниченные кванторы, применённые к примитивно рекурсивным свойствам (множествам), да­ют снова примитивно рекурсивные свойства. Это озна­чает, например, что если свойство К(х,у) примитивно рекурсивно, то свойства

г) = (Зу <С г) Щх, у)

Т(у, г) = [Уу ^ г) К(х,у)

также примитивно рекурсивны. Чтобы убедиться в этом, заметим, что для функций ограниченный квантор соот­ветствует перемножению или суммированию: если свой­ство К(х, у) равносильно г(х, у) = 0, то

S(x, z) О

А произведение легко определить рекурсивно:

П г(х,у) .у-о

0

г(х, у) = г(х, 0);

у-о

4 + 1

П г(х,у) у-о

П г(х,у) .у-ос суммированием можно поступить аналогичным обра­зом.

После этого легко заметить, что свойство «быть про­стым» примитивно рекурсивно (любое меньшее число ли­бо равно нулю, либо равно 1, либо не является делителем).

Покажем теперь, что если график некоторой функ­ции / примитивно рекурсивен и сё значения ограничены сверху некоторой примитивно рекурсивной функцией д, то сама функция / примитивно рекурсивна. В самом де­ле, если г — характеристическая функция графика, то есть r(x,y) = 1 при у = f(x) и г(х,у) = 0 при у ф f(x) (для простоты мы рассматриваем случай функций одно­го аргумента), то

оо

Дж) = Щу • г(х>у)>

а суммирование можно ограничить сверху выражени­ем д(х) и воспользоваться примитивной рскурсивностью ограниченной суммы.

Отсюда легко вывести следующее утверждение: если функция д и свойство R(x,y) примитивно рекурсивны, то функция

х и-)- f(x) = наименьшее у <С д(х), для которого R(x, у)

(если для некоторого х такого у нет, то полагаем значе­ние функции равным, скажем, д(х) + 1) будет примитив­но рекурсивной. В самом деле, график функции / легко описать с помощью ограниченных кванторов.

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

Ограниченный оператор минимизации можно исполь­зовать, чтобы убедиться, что функция х и-)- (минималь­ное простое число, большее х) примитивно рекурсивна (рассуждение Евклида о бесконечности множества про­стых чисел устанавливает, что это число не превосхо­дит х! + 1, а факториал примитивно рекурсивен). После этого функция п и-)- (п-с простое число) легко определя­ется с помощью рекурсии.