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