Пример 2 Записать корректно подстановку Решение. Пример 3 Вычислить функцию-константу: Решение. - презентация

1 Пример 2 Записать корректно подстановку Решение

2 Пример 3 Вычислить функцию-константу: Решение

3 Пример 1 Какая функция получается из g и h с помощью схемы примитивной рекурсии? g = 0, h(x, y) = x Решение Схема примитивной рекурсии без параметров:

4 Пример 1 Какая функция получается из g и h с помощью схемы примитивной рекурсии? g = 0, h(x, y) = x Пример 1 Какая функция получается из g и h с помощью схемы примитивной рекурсии? g = 0, h(x, y) = x Решение

5 Пример 1 Какая функция получается из g и h с помощью схемы примитивной рекурсии? g = 0, h(x, y) = x Пример 1 Какая функция получается из g и h с помощью схемы примитивной рекурсии? g = 0, h(x, y) = x

6 Пример 2 Доказать, что S(x, y) = x + y примитивно рекурсивная функция Решение Покажем что функцию S(x, y) можно вычислить с помощью схемы примитивной рекурсии: Необходимо указать вычислимые функции g(x) и h(x, y, z)

7 Пример 2 Доказать, что S(x, y) = x + y примитивно рекурсивная функция Пример 2 Доказать, что S(x, y) = x + y примитивно рекурсивная функция Решение

8 Пример 2 Доказать, что S(x, y) = x + y примитивно рекурсивная функция Пример 2 Доказать, что S(x, y) = x + y примитивно рекурсивная функция другая запись: Указали функции g и h для вычисления функции S(x,y) по схеме примитивной рекурсии, значит доказали требуемое

9 Пример 3 Найти S(7, 3) Решение:

10 Пример 4 Доказать, что П(x, y) = x y примитивно рекурсивная функция Решение Покажем что функцию П(x, y) можно вычислить с помощью схемы примитивной рекурсии: Необходимо указать вычислимые функции g(x) и h(x, y, z)

11 Пример 4 Доказать, что П(x, y) = x y примитивно рекурсивная функция Пример 4 Доказать, что П(x, y) = x y примитивно рекурсивная функция Решение

12 Пример 4 Доказать, что П(x, y) = x y примитивно рекурсивная функция Пример 4 Доказать, что П(x, y) = x y примитивно рекурсивная функция Решение Т.к. указали функции g и h в схеме примитивной рекурсии для вычисления функции П(x, y), то доказали требуемое