Рекурсивные функции

Примитивно рекурсивные функции

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

$0(x) = 0$ (тождественный нуль);
$S(x) = x + 1$ (инкремент);
$I_n^m(x_1, x_2, \ldots, x_n) = x_m$ (оператор выбора аргумента).

Операторы:

Суперпозиция функций.

Пусть задана функция $h(x_1, x_2, \ldots, x_m)$. Подставим в качестве ее аргументов результаты вычисления функций $q_1(x_1, x_2, \ldots, x_n), \ldots, q_m(x_1, x_2, \ldots, x_n)$, в результате получим функцию $\varphi(x_1, \ldots, x_n) = h(q_1(x_1, \ldots, x_n), \ldots, q_m(x_1, \ldots, x_n)).$

Примитивная рекурсия.

Пусть заданы функции $h(x_1, x_2, \ldots, x_n)$ и $\varphi(x_1, x_2, \ldots, x_n, y, z)$. Схема примитивной рекурсии указывает, как выразить значение функции с аргументом $y+1$ через значение той же функции с аргументом $y$: $f(x_1, \ldots, x_n, 0) = h(x_1, \ldots, x_n),$ $f(x_1, \ldots, x_n, y+1) = \varphi(x_1, \ldots, x_n, y, f(x_1, \ldots, x_n, y)).$ В частном случае $n = 0$: $f(0) = a,\quad f(y + 1) = \varphi(y, f(y)).$

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

Функция вида $f \colon X \to Y$ называется частичной, если она определена не для всех $x \in X$.

Класс частично рекурсивных функций получается добавлением к определению класса примитивно рекурсивных функций оператора минимизации.

Пусть задана функция $f(x,y)$. Фиксируя значение $x$, выясняем при каком наименьшем $y$ выполняется равенство $f(x,y) = 0$. Результат является функцией от $x$ и обозначается $\varphi(x) = \mu y[f(x,y) = 0].$

Аналогично оператор минимизации определяется и для функции нескольких переменных: $\varphi(x_1, \ldots, x_n) = \mu y[f(x_1, \ldots, x_n, y) = 0].$

Функция называется общерекурсивной, если она частично рекурсивна и всюду определена.

Тезис А. Чёрча. Каждая интуитивно вычислимая функция является частично рекурсивной.

Этот тезис нельзя доказать, т. к. он связывает нестрогое математическое понятие интуитивно вычислимой функции со строгим математическим понятием частично рекурсивной функции. Но этот тезис может быть опровергнут, если построить пример функции интуитивно вычислимой, но не являющейся частично рекурсивной [Лихтарников, с. 146].

Однако для функций, вычислимых на компьютере, можно провести некоторый анализ, который устанавливает, что любая функция, вычисленная при помощи композиции операторов присваивания и конструкций if, for и while окажется частично рекурсивной. Наводящие соображения: почти любая программа, в силу того, что инструкций обычно гораздо меньше, чем их выполнений, содержит повторяющиеся вычисления, которые и приводят к рекурсии. В данном случае итерационный процесс – это тоже рекурсия. Оператор for можно представить в виде частичной рекурсии, примененной к функции, которая преобразует значения переменных за одну итерацию. Оператор if сводится к вычислению предиката логического условия и вызову функции от аргумента 0 или 1. Оператор while можно выразить с помощью неограниченной минимизации. Таким образом, любая программа вычислит частично рекурсивную функцию.

Вычислимость по Тьюрингу

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

Литература

Лихтарников, Сукачева – Математическая логика. Курс лекций. Задачник-практикум и решения (2009)

Пруцков, Волкова – Математическая логика и теория алгоритмов (2018)

Гринченков, Потоцкий – Математическая логика и теория алгоритмов для программистов (2010) – С. 86

Верещагин, Шень – Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления (2012)