LOGO Рекурсивные функции Простейшие функции Операция суперпозиции. - презентация

1 LOGO Рекурсивные функции Простейшие функции Операция суперпозиции

2 Алгоритмический процесс можно рассматривать как процесс вычисления значений некоторой функции f Такие функции называются вычислимыми

3 Интуитивное понятие вычислимой функции заменим на точное понятие частично рекурсивной функции

4 Рассмотрим некоторый набор простейших функций, вычислимость которых очевидна Простейшие функции Простейшими функциями называются следующие арифметические функции: 1) Нулевая функция О n (x 1, x 2, …, x n ) = 0 O(x) = 0 2) Функция следования (x) = x + 1, x N 3) Функция проецирования (выбора) I m n (x 1, x 2, …, x n ) = x m Вспомните понятие арифметической функции

5 Замечание Вычислимость функции проецирования обеспечивается нашей способностью найти в строке (x 1, x 2, …, x n ) место с номером m и указать число на этом месте

6 Пусть заданы арифметические функции: f 1 (x 1, x 2, …, x n ), f 2 (x 1, x 2, …, x n ), …, f m (x 1, x 2, …, x n ), (y 1, y 2, …, y m ) Операция подстановки (суперпозиции) Говорят, что функция (x 1, x 2, …, x n ) получена из функций и f 1, f 2, …, f m операцией подстановки (суперпозиции), если: Обозначение:

7 Пример 1 Операция подстановки (суперпозиции)

8 Пример 1 Операция подстановки (суперпозиции)

9 Правильное применение суперпозиции: необходимо соблюдать требования к набору аргументов каждой функции Операция подстановки (суперпозиции)

10 Пример 1 Операция подстановки (суперпозиции) Преобразуем функции f 1 и f 2 так, чтобы они удовлетворяли требованиям к аргументам для применения суперпозиции Корректно

11 Замечание Такое применение функции проецирования предложил К.Гёдель (1934) Все функции f i, i = 1,…m зависят от n переменных, а функция имеет m переменных (по количеству функций f i ) Результат подстановки, функция зависит от n переменных

12 Добиться выполнение условия на количество аргументов у функций можно введением фиктивных переменных и применения функции проецирования I m n

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

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

15 Литература 1.Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, с. 2.Теория алгоритмов / Электронный учебник 3.Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. - СПб.: Лань, с.

16 Нельзя научить, можно научиться