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