Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Основывается на простейших или выведенных из простейших функциях g и h:
Пусть
Тогда новая функция может быть выведена по правилу:
(4.6)
Следует отметить, что функция зависит от аргументов, функция зависит от аргументов, функция зависит от аргументов. Иначе говоря, правило примитивной рекурсии позволяет получить n + 1 -местную функцию из n -местной и n + 2 - местной функций.
ПРИМЕР
Пусть некоторая функция задана правилом рекурсии
Нетрудно заметить, что функция , функция
Вычислим значение функции при .
Нетрудно заметить, что функция выполняет сложение двух чисел и .
3. m - оператор (оператор нахождения наименьшего корня у)
Оператор определяет наименьшее значение у, при котором при фиксированном значении. Принято обозначение
(4.7)
(Читается: «наименьшее такое, что »). Аналогично определяется функция многих переменных:
(4.8)
Для вычисления функции существует следующий алгоритм:
1. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу.
2. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу. И т. д.
Если окажется, что для всех функция , то функция считается неопределенной.
ПРИМЕР
Дана функция . Необходимо определить при
Таким образом,
Функция называется частично рекурсивной, если она получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии или m - оператора.
Функция называется примитивно рекурсивной, если она может быть получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии.
Функция называется общерекурсивно й, если она частично рекурсивная и всюдуопределенная.
Тезис А. Черча. Если функция является общерекурсивной, то она выполнима, т.е. имеет алгоритм решения.
Дата публикования: 2014-11-03; Прочитано: 349 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!