Частично рекурсивные функции
РЕКУРСИВНЫЕ ФУНКЦИИ
В данной части пособия рассматриваются вопросы, связанные с понятием вычислимости. Приводится формальное уточнение интуитивного понятия вычислимой функции в виде определения частично рекурсивных функций. Изучаются некоторые важные свойства таких функций.
ВЫЧИСЛИМЫЕ ФУНКЦИИ
Вычислительные возможности таких устройств, как схемы из функциональных элементов или конечные автоматы, являются ограниченными, поскольку существуют интуитивно вычислимые числовые функции, которые не могут вычисляться в перечисленных моделях.
Например, как было доказано, конечными автоматами не может вычисляться функция умножения неотрицательных целых чисел.
В самом общем случае единый метод вычисления значений произвольной функции, который может выполняться механически, на основе явной системы правил, называется алгоритмом или эффективной процедурой.
Сама такая функция называется эффективно вычислимой.
Алгоритм это всегда конечное и формальное описание процесса вычисления значений функции для произвольных начальных данных вместе с правилами применения этого описания для выполнения вычислений.
Существуют разные формальные средства для описания алгоритмов и механизмы их выполнения.
В частности, к ним относятся языки программирования.
Для изучения общих свойств алгоритмов и вычисляемых ими функций такие языки неудобны, так как обладают избыточностью и перегружены деталями, обусловленными требованиями удобства практического применения или ясности.
Всякая программа может рассматриваться как отображение множества возможных значений начальных данных во множество значений результатов программы.
Множество начальных данных для алгоритма обычно является счетно-бесконечным.
Естественно рассматривать любую программу лишь с точки зрения соотношения значений в начале её работы и значений при окончании работы. Тогда всякой программе Pможно поставить в соответствие функцию fP: A ® B, которая отображает исходные данные программы в результаты ее работы.
Эта функция вычислима, поскольку для любого значения ее аргумента a Î Aзначение fP(a) может быть вычислено путем выполнения программы P.
Функция fP, вычисляемая программой P, может быть не всюду определенной, т.е. являться частичной функцией. Такая ситуация может иметь место для некоторого начального данного в том случае, когда вычисление, выполняемое соответствующей программой никогда не заканчивается.
В общем случае ситуация с незавершающимся вычислением допускает интерпретацию в виде бесконечного процесса поиска ответа для решаемой задачи. При этом решение задачи или значение функции не может быть найдено за конечное время.
Множества Aи Bобычно являются счетно-бесконечными и для общего исследования вычислимости могут рассматриваться как множества целых неотрицательных чисел.
Действительно, элементы A и Bможно рассматривать как семейства двоичных записей, представляющих целые неотрицательные числа. В таких числах допускаются незначащие нули.
Поэтому функция fP, вычисляемая произвольной программой P, - это числовая функция fP: Nk ® N.
То есть здесь будет принято считать, что начальные данные всякой программы представляют собой числовые наборы некоторой длины.
Результат работы программы также представляет некоторое целое неотрицательное число.
Заметим, что вычисления, порождаемые алгоритмами, не всегда являются конечными. Бесконечность вычисления означает, что значение соответствующей функции для начальных данных не определено.
ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ
Определим формальную систему, в которой определяются вычислимые числовые функции, отображающие числа из N или наборы чисел из N во множество N.
8.2.1. Простейшие функции
Следующие функции называются простейшими:
тождественный ноль О(x) = 0;
функция следования S(x) = x + 1;
функции проекции 
(x1, ... , xn), где 1 
m 
n.
Все эти функции являются вычислимыми, поскольку могут вычисляться с помощью очевидных алгоритмов.
8.2.2. Элементарные функции
Пусть заданы функции:
f(x1, . . . , xk), gi(xi1, . . . , xim i), i = 1, . . . , k.
Функция h(xj1, . . . , xjr) получается из заданных функций с помощью операции суперпозиции, если её можно представить в виде выражения:
f(g1(x1,1, . . . , x1,m1), . . . , gk(xk,1, . . . , xk,mk)).
Здесь переменными функции h являются все различные переменные функций gi(xi,1, . . . , xi,mi), i = 1, . . . , k.
Если все функции f(x1, . . . , xn), gi(xi1, . . . , ximi), i = 1, . . . , k, являются вычислимыми, то вычислима и суперпозиция таких функций - функция h.
ОПРЕДЕЛЕНИЕ
Функции, получаемые из простейших функций с помощью конечного числа применений операции суперпозиции, называются элементарными функциями.
Всякая элементарная функция является вычислимой.
Пример. Функция f(x) = x + 2 является элементарной, так как f(x) = S(S(x)).
Элементарными являются, в частности, все функции константы.
Например, функция f(x) = k , где k - некоторое число из N, может быть выражена следующей суперпозицией:
S(...S(O(x)...), в которой функция следования S применяется k раз.
Упражнение. Показать, что если f(x1, . . . , xn) - это элементарная функция, то она растет не быстрее, чем некоторая линейная функция.
Существуют вычислимые числовые функции, которые не являются элементарными.
Например, функция f(x) = x2 не является элементарной.