Т. А. Сливина математическая логика и теория алгоритмов

§ 4. Вычислимые функции. Частично рекурсивные и общерекурсивные функции
Для алгоритмических проблем типичным является то обстоятельство, что требуется найти алгоритм для решения задачи, в условия которой входят значения некоторой конечной системы целочисленных параметров x₁, х₂, ..., х_п, а искомым результатом также является целое число у. Следовательно, стоит вопрос о существовании алгоритма для вычисления значений числовой функции у, зависящей от целочисленных значений аргументов x₁, х₂, ..., х_п.
Определение 1. Функция g = f(x₁, x₂,..., х_п) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения.
Так как в этом определении алгоритм понимается в интуитивном смысле, то и понятие эффективно вычислимой функции является интуитивным.
Однако переход от алгоритма к эффективно вычислимой функции дает определенные преимущества. Дело в том, что те требования, которые предъявляются к алгоритму в его характерных чертах, выполняются для совокупности всех вычислимых функций, которая носит название совокупности рекурсивных функций.
Гёдель впервые описал класс всех рекурсивных функций как класс всех числовых функций, определяемых в некоторой формальной системе. Черч в 1936 году пришел к тому же классу функций, исходя из других предпосылок. Здесь построение класса вычислимых функций строится следующим образом.
Выбираются простейшие функции


(оператор сдвига),
О(х) = 0 (оператор аннулирования),
(оператор проектирования).

Ясно, что все три простейшие функции всюду опре­делены и интуитивно вычислимы.

Далее вводятся операции над функциями.
1. Суперпозиция функций.
Рассмотрим функции и функцию , функцию , определяемую равенством


.
Будем говорить, что функция получена из функций и f₁, f₂, ..., f_m суперпозицией.
Если мы каким-либо образом умеем вычислять функции f₁, f₂, ..., f_m , то функция может быть вычислена так: придадим переменным x_v х₂, ..., х_п некоторые значения a₁, а₂, ..., а_п. Вычисляя все , найдем . Вычисляя теперь найдем .
Ясно, что если все функции f_l, f₂, ..., f_m и всюду определены, то функция всюду определена. Функция будет не всюду определенной, если хотя бы одна из функций f_l, f₂, ..., f_m не всюду определена, или если можно найти такие значения аргументов а₁, а₂, ..., а_n, что b_i=f_i(a₁,a₂,...,a_n), но (b₁,b₂,.,.,b_m) не определено (i = 1,…, т).
Таким образом, если функции f_l, f₂, ..., f_m, интуитивно вычислимы, то будет интуитивно вычислима и функция .
Отметим, что возможны случаи, когда не все функции f₁, f₂, ..., f_m зависят от всех п аргументов х₁, x₂, ..., х_п. В этих случаях для получения суперпозиции используются фиктивные аргументы и функции . Например, функция получается суперпозицией из функций и


.