Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 10 стр.

        2.5. Методика решения задач

        2.5.1. Использование оператора примитивной рекурсии
    Пример 1. Доказать примитивную рекурсивность функции f(x, y) = x + y.
    Решение. Рассмотрим способ рекурсивного определения данной функции:
    f(x, 0) = x,
    f(x, y+1) = x + y + 1 = f(x, y) +1.
    Чтобы показать соответствие данной рекурсивной схемы схеме примитивной рекурсии,
воспользуемся функциями выбора и следования:
    f(x, 0) = x = I(x),
    f(x, y+1) = f(x, y) + 1 = S(f(x, y)) = S(I3(x, y, f(x, y))).

    Пример 2. Доказать примитивную рекурсивность функции f(x, y) = x ⋅ y.
    Решение. Рассмотрим способ рекурсивного определения данной функции:
    f(x, 0) = 0,
    f(x, y+1) = x ⋅ (y + 1) = x ⋅ y + x = f(x, y) +x,
из которого следует, что Z(x) = x ⋅ 0.
    Обозначим x ⋅ y = p(x, y), тогда:
    p(x, 0) = Z(x);
    p(x, y+1) = p(x, y) +x = S(p(x, y), x) = S( I 13 (x, y, p(x, y)), I 33 (x, y, p(x, y))).

    Пример 3. Доказать примитивную рекурсивность функции
                                                          0, если x = 0,
                                               Sg ( x ) = 
                                                          1, если x ≠ 0.
    Решение. Рассмотрим способ рекурсивного определения данной функции:
    Sg(0) = 0 = Z(x),
    Sg(x+1) = Z(x) +1 = 1 = S(Z(x)).

    Пример 4. Доказать примитивную рекурсивность функции f(x) = 2x.
    Решение. Рассмотрим способ рекурсивного определения данной функции:
    f(0) = 1 = S(Z(x)),
    f(x+1) = 2 ⋅ 2x =2 ⋅ f(x) = S(S(Z(x))).

    Пример 5. Доказать примитивную рекурсивность функции f(x, y) = xy.
    Решение. Рассмотрим способ рекурсивного определения данной функции:
    f(x, 0) = 1 = S(Z(x));
    f(x, y+1) = xy+1 = xy ⋅ x = f(x, y) ⋅ I 12 (x, y) = p( I 33 (x, y, f(x, y)), I 13 (x, y, f(x, y))).

        2.5.2. Использование оператора минимизации
   Пример 1. Пусть f(x, y) = µz( 2⋅x + z = y+1), откуда предикат P(x, y, z) = 2⋅x + z = y + 1.
   Покажем примитивную рекурсивность предиката P. Его характеристическая функция
может быть представлена следующим выражением:
   Sg(Sg((2 ⋅ x + z) ÷( y + 1)) + Sg((y +1) ÷ (2 ⋅ x + z)).
   Найдем значение функции в точке (1, 5):
   При z = 0: P(1, 5, 0) = 2 ⋅ 1 + 0 = 5 + 1 - "ложь",
       z = 1: P(1, 5, 1) = 2 ⋅ 1 + 1 = 5 + 1 - "ложь",
       z = 2: P(1, 5, 1) = 2 ⋅ 1 + 2 = 5 + 1 - "ложь",
       z = 3: P(1, 5, 1) = 2 ⋅ 1 + 3 = 5 + 1 - "ложь",
       z = 4: P(1, 5, 4) = 2 ⋅ 1 + 4 = 5 + 1 - "истина".