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

UptoLike

Составители: 

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(I
3
(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(
3
1
I (x, y, p(x, y)),
3
3
I
(x, y, p(x, y))).
Пример 3. Доказать примитивную рекурсивность функции
=
=
0. xесли ,1
0, xесли ,0
)x(Sg
Решение. Рассмотрим способ рекурсивного определения данной функции:
Sg(0) = 0 = Z(x),
Sg(x+1) = Z(x) +1 = 1 = S(Z(x)).
Пример 4. Доказать примитивную рекурсивность функции f(x) = 2
x
.
Решение. Рассмотрим способ рекурсивного определения данной функции:
f(0) = 1 = S(Z(x)),
f(x+1) = 2 2
x
=2 f(x) = S(S(Z(x))).
Пример 5. Доказать примитивную рекурсивность функции f(x, y) = x
y
.
Решение. Рассмотрим способ рекурсивного определения данной функции:
f(x, 0) = 1 = S(Z(x));
f(x, y+1) = x
y+1
= x
y
x = f(x, y)
2
1
I
(x, y) = p(
3
3
I
(x, y, f(x, y)),
3
1
I (x, y, f(x, y))).
2.5.2. Использование оператора минимизации
Пример 1. Пусть f(x, y) = µ
z
( 2x + z = y+1), откуда предикат P(x, y, z) = 2x + 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 - "истина".