Для алгоритмических проблем типичным является то обстоятельство, что требуется найти алгоритм для решения задачи, в условия которой входят значения некоторой конечной системы целочисленных параметров \(x_{1}, x_{2},...,x_{n}\), а искомым результатом также является целое число \(y\). Следовательно, стоит вопрос о существовании алгоритма для вычисления значений числовой функции \(y\), зависящей от целочисленных значений аргументов \(x_{1}, x_{2},...,x_{n}\).
Функция \(g=f (x_{1},x_{2},...,x_{n})\) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения.
Так как в этом определении алгоритм понимается в интуитивном смысле, то и понятие эффективно вычислимой функции является интуитивным.
Однако переход от алгоритма к эффективно вычислимой функции дает определенные преимущества. Дело в том, что те требования, которые предъявляются к алгоритму в его характерных чертах, выполняются для совокупности всех вычислимых функций, которая носит название совокупности рекурсивных функций.
Гедель впервые описал класс всех рекурсивных функций как класс всех числовых функций, определяемых в некоторой формальной системе. Черч в 1936 году пришел к тому же классу функций, исходя из других предпосылок. Здесь построение класса вычислимых функций
строится следующим образом.
Выбираются простейшие функции:
1) \(\lambda (x) = x+1\) (оператор сдвига);
2) \(O (x) =0\) (оператор аннулирования);
3) \(I^{m}_{n} (x_{1},x_{2},...,x_{n}) =x_{m}\), \(1\leq m\leq n\) (оператор проектирования).
Ясно, что все три простейшие функции всюду определены и интуитивно вычислимы.
Далее вводятся операции над функциями.
1. Суперпозиция функций.
Рассмотрим функции \(f_{1} (x_{1},x_{2},...,x_{n})\), \(f_{2} (x_{1},x_{2},...,x_{n})\),..., \(f_{m} (x_{1},x_{2},...,x_{n})\) и функцию \(\varphi (x_{1},x_{2},...,x_{m})\); функцию \(\psi (x_{1},x_{2},...,x_{n})\), определяемую равенством
$$\psi (x_{1},x_{2},...,x_{n}) =$$
$$= \varphi (f_{1}(x_{1},x_{2},...,x_{n}),f_{2}(x_{1},x_{2},...,x_{n}),...,f_{m}(x_{1},x_{2},...,x_{n})).$$
Будем говорить, что функция \(\psi\) получена из функций \(\varphi\) и \(f_{1},f_{2},...,f_{m}\) суперпозицией.
Если мы каким-либо образом умеем вычислять функции \(f_{1},f_{2},...,f_{m}\) и \(\varphi\), то функция \(\psi\) может быть вычислена так: придадим переменным \(x_{1},x_{2},...,x_{n}\) некоторые значения \(a_{1},a_{2},...,a_{n}\). Вычисляя все \(f_{i} (a_{1},a_{2},...,a_{n})\), найдем \(b_{i}= f_{i} (a_{1},a_{2},...,a_{n})\). Вычисляя теперь \(\varphi (b_{1},b_{2},...,b_{m})\) найдем \(c= \psi (a_{1},a_{2},...,a_{n})\).
Ясно, что если все функции \(f_{1},f_{2},...,f_{m}\) и \(\varphi\) всюду определены, то функция \(\psi\) всюду определена. Функция \(\psi\) будет не всюду определенной, если хотя бы одна из функций \(f_{1},f_{2},...,f_{m}\) не всюду определена, или если можно найти такие значения аргументов \(a_{1},a_{2},...,a_{n}\), что \(b_{i}=f_{i}(a_{1},a_{2},...,a_{n})\), но \(\varphi (b_{1},b_{2},...,b_{m})\) не определено \(( i = \overline {1,m} ).\)
Таким образом, если функции \(f_{1},f_{2},...,f_{m}, \varphi\) интуитивно вычислимы, то будет интуитивно вычислима и функция \(\psi\).
Отметим, что возможны случаи, когда не все функции \(f_{1},f_{2},...,f_{m}\) зависят от всех \(n\) аргументов \(x_{1},x_{2},...,x_{n}\). В этих случаях для получения суперпозиции используются фиктивные аргументы и функции \(I^{m}_{n} (x_{1},x_{2},...,x_{n})\). Например, функция \(\psi (x,y,z) = \varphi ( f_{1}(x), f_{2}(x,y,z), y,x)\) получается суперпозицией из функций \(\varphi (x_{1},x_{2},x_{3},x_{4})\) и \(F_{1}(x,y,z)= f_{1}(x)\), \(F_{2}(x,y,z)= f_{2}(x,y,z)\), \(F_{3}(x,y,z)= I^{2}_{3}(x,y,z)\), \(F_{4}(x,y,z)= I^{1}_{3}(x,y,z)\).
2. Схема примитивной рекурсии. Пусть имеются две функции \(\varphi (x_{2},x_{3},...,x_{n})\) и \(\psi (x_{1},x_{2}, ...,x_{n},x_{n+1})\) \((n>1)\). Рассмотрим новую функцию, которая удовлетворяет следующим равенствам:
| $$f(0, x_{2},x_{3},...,x_{n})=\varphi (x_{2},x_{3},...,x_{n}),$$ $$f(y+1, x_{2},x_{3},...,x_{n})=\psi (y,f(y,x_{2},x_{3},...,x_{n}),x_{2},...,x_{n}).$$ | (1) |
Если функция \(f (x_{1},x_{2},...,x_{n})\) получается из функций \(\varphi\) и \(\psi\) с помощью равенств (1), то говорят, что функция \(f\) получена из функций \(\varphi\) и \(\psi\) по схеме примитивной рекурсии.
Если функции \(\varphi\) и \(\psi\) интуитивно вычислимы, то будет интуитивно вычислима и функция \(f\). Действительно, пусть \(a_{1}, a_{2},...,a_{n}\) набор значений аргументов \(x_{1}, x_{2},...,x_{n}\). Тогда последовательно находим: $$f(0, a_{2}, a_{3},...,a_{n} ) = \varphi (a_{2}, a_{3},...,a_{n} ) = b_{0},$$ $$f(1, a_{2}, a_{3},...,a_{n} ) = \psi (0,b_{0},a_{2}, a_{3},...,a_{n} ) = b_{1},$$ $$f(2, a_{2}, a_{3},...,a_{n} ) = \psi (1,b_{1},a_{2}, a_{3},...,a_{n} ) = b_{2} ....$$
Очевидно, что если функции \(\varphi\) и \(\psi\) всюду определены, то будет всюду определена и функция \(f\).
Рассмотрим примеры получения функций по схеме примитивной рекурсии.
Пример 1. Пусть функция \(f (x,y)\) задана равенствами: $$\begin{cases} f(0,x) =x, \\ f(y+1,x = f (y,x) +1. \end{cases}$$
Здесь функция \(\varphi (x) =x\), a \(\psi (x,y,z) =y+1\).
Вычислим значение функции\(f(y,x)\) при \(y=5, x=2\). Так как \(f(0,2)=\varphi (2)=2\), то из второго равенства последовательно имеем: $$\begin{cases} f(1,2)=\psi (0,2,2)=2+1=3 \\ f(2,2)=\psi (1,3,2)=3+1=4 \\ f(3,2)=\psi (2,4,2)=4+1=5 \\ f(4,2)=\psi (3,5,2)=5+1=6 \\ f(5,2)=\psi (4,6,2)=6+1=7 \end{cases}$$
Нетрудно показать, что \(f (y,x) = y+x\). Действительно, \(f (y+z,x) = f(y,x) +z\). Полагая в этом равенстве \(y=0\), получим \(f(z,x) = f(0,x)+z\) или \(f(z,x) = x+z\).
Пример 2. Пусть функция \(f(y,x)\) задана равенствами: $$\begin{cases} f (0,x)=0, \\ f(y+1,x) = f(y,x)+x. \end{cases}$$
Здесь \(\varphi (x)=0\), \(\psi (x,y,z) = y+z\).
Вычислим значение функции \(f(y,x)\) при \(y=2, x=2\). Так как \(f(0,x)=\varphi (x)=0\), то \(f(0,2)=0\), а значения \(f(1,2)\) и \(f(2,2)\) находим последовательно: $$\begin{cases} f(1,2)=\psi (1,0,2)=0+2=2 \\ f(2,2) = \psi (2,2,2)=2+2=4 \end{cases}$$
Легко показать, что в этом примере \(f(y,x)= x\cdot y\). Действительно, \(f(y+z,x)= f(y,x) + z\cdot x\). Полагая в этом равенстве \(y=0\), получим \(f(z,x)= f(0,x) + z\cdot x\) или \(f(z,x)= z\cdot x\).
3. Операция минимизации (\(\mu\)-оператор).
Пусть задана некоторая функция \(f(x,y)\). Зафиксируем значение \(x\) и выясним, при каком значении \(y)\) \(f(x,y)=0\).
Более сложной задачей является отыскание для данной функции \(f(x,y)\) и фиксированного \(x\) наименьшего из тех значений \(y\), при которых функция \(f(x,y)=0\). Так как результат решения задачи зависит от \(x\), то наименьшее значение \(y\), при котором функция \(f(x,y)=0\) есть функция \(x\). Принято обозначение $$\varphi (x)=\mu y\left[f(x,y)=0 \right] .$$
(Читается: "наименьшее \(y\) такое, что {\(f(x,y)=0\)".)
Аналогично можно определить функцию для многих переменных: $$\varphi (x_{1},x_{2},...,x_{n})=\mu y\left[f(x_{1},x_{2},...,x_{n},y)=0 \right]$$
Переход от функции \(f(x_{1},x_{2},...,x_{n},y)\) к функции \(\varphi (x_{1},x_{2},...,x_{n})\) называется применением \(\mu\)-оператора.
Для вычисления функции \(\varphi\) можно предложить следующий алгоритм:
1. Вычислим \(f(x_{1},x_{2},...,x_{n},0)\). Если это значение \(f=0\), то полагаем \(\varphi (x_{1},x_{2},...,x_{n})=0\). Если \(f(x_{1},x_{2},...,x_{n},0)\neq 0\), то переходим к следующему шагу.
2. Вычислим \(f(x_{1},x_{2},...,x_{n},1)\). Если это значение \(f(x_{1},x_{2},...,x_{n},1)=0\), то полагаем \(\varphi (x_{1},x_{2},...,x_{n})=1\). Если же \(f(x_{1},x_{2},...,x_{n},1)\neq 0\), то переходим к следующему шагу. И так далее.
Пример 3. Рассмотрим функцию \(f(x,y)=x-y\), которая может быть получена с помощью оператора минимизации $$f(x,y)=\mu z(y+z=x)=\mu z\left[I^{2}_{3}(x,y,z) +I^{3}_{3}(x,y,z)=I^{1}_{3}(x,y,z) \right].$$
Вычислим, например, \(f(7,2)\), то есть значение функции при \(y=2, x=7\). Для этого положим \(y=2\) и будем придавать \(x\) последовательно значения:
| $$z=0,$$ | $$2+0=2\neq 7,$$ |
| $$z=1,$$ | $$2+1=3\neq 7,$$ |
| $$z=2,$$ | $$2+2=4\neq 7,$$ |
| $$z=3,$$ | $$2+3=5\neq 7,$$ |
| $$z=4,$$ | $$2+4=6\neq 7,$$ |
| $$z=5,$$ | $$2+2=7=7.$$ |
Таким образом, \(f(7,2)=5\).
Функция \(f(x_{1},x_{2},...,x_{n})\) называется частично рекурсивной, если она может быть получена за конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и \(\mu\)-оператора.
Функция \(f(x_{1},x_{2},...,x_{n})\) называется общерекурсивной, если она частично рекурсивна и всюду определена.
Примерами общерекурсивных функций являются:
1) \(\lambda (x)\);
2) \(O (x)\);
3) \(I^{m}_{n} (x)\);
4) \(f(y,x)=y+x\);
5) \(f(y,x)=x\cdot y\);
6) \(f(y,x)=x+n\).
Тезис А. Чёрча. Каждая интуитивно вычислимая функция является частично рекурсивной.
Этот тезис нельзя доказать, так как он связывает нестрогое математическое понятие интуитивно вычислимой функции со строгим математическим понятием частично рекурсивной функции.
Но этот тезис можно опровергнуть, если построить пример функции интуитивно вычислимой, но не являющейся частично рекурсивной.
