Содержание
- 2. Вычислимые функции
- 3. Алгоритмы: определение и основные свойства Понятие алгоритма является одним из основных понятий современной математики. Само слово
- 4. Предписание считается алгоритмом, если оно обладает следующими свойствами: • определенностью, то есть общепонятностью и точностью, не
- 5. Каждый алгоритм, в общем случае, должен задаваться следующими параметрами: • множеством допустимых исходных данных, • начальным
- 6. Необходимость уточнения понятия алгоритма Длительное время интуитивного понятия алгоритма было вполне достаточно для задач математики и
- 7. Формализации Черча, Тьюринга и Маркова. В двадцатых годах XX века задача точного определения понятия алгоритма стала
- 8. С точки зрения английского математика А.Тьюринга алгоритмический процесс — это работа некоторой воображаемой вычислительной машины —
- 9. Каждый из этих вариантов определения понятия алгоритма фиксирует свой класс K рассматриваемых объектов, свои правила переработки,
- 10. Счетные множества. Напомним некоторые сведения о счетных множествах. Множество A называется равномощным множеству B, если существует
- 11. Отметим следующие известные свойства счетных множеств. 1) Подмножество счетного множества конечно или счетно. 2) Объединение конечного
- 12. Арифметическая функция – функция, определенная на множестве натуральных чисел и принимающая значения из множества натуральных чисел.
- 13. Предположим противное. Пусть арифметических функций одной переменной счетное множество, т.е. их можно перечислить. Тогда их можно
- 14. Однако по построению g(x) принадлежит множеству арифметических функций одной переменной, значит должна быть в списке перечисления
- 15. Алгоритмы и функции. Вариант строгого определения алгоритма, предложенный Черчем и Клини, рассматривает алгоритмический процесс как процесс
- 18. Оператор суперпозиции S. Рассмотрим действие, которое назовем оператором суперпозиции (регулярной суперпозиции). С помощью этого действия из
- 19. Оператор примитивной рекурсии R. Рассмотрим действие, которое назовем оператором примитивной рекурсии. С помощью оператора примитивной рекурсии
- 20. Если все значения в правых частях равенств существуют, то получим значение функции f (x1, x2,...,xn, m
- 21. Функция f называется примитивно-рекурсивной, если ее можно получить конечным числом операций подстановки и примитивной рекурсии, исходя
- 23. Пример 3. Постоянная унарная функция f (x) = a примитивно рекурсивна. Доказательство. Имеем запись f (x)
- 26. Утверждение. Функция сложения f (x, y) = x + y примитивно рекурсивна. Доказательство. Покажем, что функция
- 27. Утверждение. Функция умножения f (x, y) = x∙y примитивно рекурсивна. Доказательство. Как и в предыдущем предложении
- 29. Определение. Арифметическая функция f называется примитивно рекурсивной функцией (ПРФ), если существует ПРО, последней функцией которого f
- 30. Определение. Пусть H есть конечная совокупность функций. Примитивно рекурсивное описание относительно совокупности функций H есть конечная
- 31. Cвойства ПРО относительно совокупности функций H. 1. Если функция f примитивно рекурсивна относительно совокупности функций H,
- 32. 4. Примитивно рекурсивная функция примитивно рекурсивна относительно любой совокупности функций. 5. Если функция f примитивно рекурсивна
- 33. Функции, представимые термами Формальные символы 1. f1, f2,..., f3 - символы для арифметических функций. 2. 0,1,2,...
- 35. Шаг индукции. Покажем, что функция fk(t1,...,tnk), представимая термом fk(t1,...,tnk) ранга r, примитивно рекурсивна относительно совокупности функций
- 37. Рекурсивные определения знакомы математику. Например, функция f, определяемая соотношениями fО) = 1, f(1) = 1, f(x
- 38. Примитивнорекурсивные функции — это пример широкого и интересного класса всюду определенных функций, который можно получить подобной
- 39. К сожалению, можно построить и всюду определенные функции с очевидными алгоритмами, которые нб являются примитивно- рекурсивными.
- 42. Скачать презентацию