Примитивно рекурсивные функции (ПРФ)

Частично-рекурсивные функции

Базисные функции: нулевая, следования, проекции. Операторы суперпозиции и примитивной рекурсии. Примитивно-рекурсивные функции. Оператор минимизации. Частично-рекурсивные функции. Тотально-рекурсивные функции. Примеры примитивно (частично, тотально)-рекурсивных функций. Тезис Черча

Рекурсия - один из основных приемов программирования.

Рекурсивная функция (от лат. recursio – возвращение) – это числовая функция  числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения , , ….

При разработке машин Тьюринга было отмечено, что команда, которую выполняет машина в последующий момент автоматного времени зависит от содержимого ячейки и внутреннего состояния в предыдущий момент времени. Так реализуется автоматная память. В теории рекурсивных функций, которая считается исторически первой формализацией понятия алгоритма, применяется нумерация слов в произвольном алфавите натуральными числами (N), и любой алгоритм сводится к вычислению некоторой функции при целочисленных значениях аргументов.

Функция вычислима, если существует такой алгоритм, то есть пошаговая процедура «от простого к сложному», которая по входному набору переменных вычисляет значение функции, если этот входной набор принадлежит к области определения функции, или выдает сообщение, что входной набор не принадлежит к области определения функции.

Функция полувычислима, если при задании входного набора, не принадлежащего области определения функции, алгоритм не заканчивает работу («зацикливается»). Теорию вычислимости разрабатывал А. Черч. Идея теории состоит в выделении элементарных вычислимых функций (которые «интуитивно вычислимы») – то есть базиса и разработке средств получения из этих элементарных вычислимых функций более сложных функций за конечное число шагов. Полученные таким образом функции тоже будут вычислимы.

Примитивно рекурсивные функции (ПРФ)

Определение

Элементарными функциями называются:

1) функция константы , где ,

2) функция следования

3) функция выбора , где .

Операция подстановки

Пусть задана функция  и функции , , …, .

Определение

Говорят, что функция  получена из этих функций с применением операции подстановки, если выполняется следующее равенство:

=

и обозначается:

,

где  - операция подстановки.