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

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

8.1. Вычислимые функции

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

Например, как было доказано, конечными автоматами не может вычисляться функция умножения неотрицательных целых чисел.

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

Сама такая функция называется эффективно вычислимой.

Алгоритм это всегда конечное и формальное описание процесса вычисления значений функции для произвольных начальных данных вместе с правилами применения этого описания для выполнения вычислений.

Существуют разные формальные средства для описания алгоритмов и механизмы их выполнения.

В частности, к ним относятся языки программирования.

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

Всякая программа может рассматриваться как отображение множества возможных значений начальных данных во множество значений результатов программы.

Множество начальных данных для алгоритма обычно является счетно-бесконечным.

Естественно рассматривать любую программу лишь с точки зрения соотношения значений в начале её работы и значений при окончании работы. Тогда всякой программе P можно поставить в соответствие функцию f_P: A  B, которая отображает исходные данные программы в результаты ее работы.

Эта функция вычислима, поскольку для любого значения ее аргумента a  A значение f_P(a) может быть вычислено путем выполнения программы P.

Функция f_P, вычисляемая программой P, может быть не всюду определенной, т.е. являться частичной функцией. Такая ситуация может иметь место для некоторого начального данного в том случае, когда вычисление, выполняемое соответствующей программой никогда не заканчивается.

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

Множества A и B обычно являются счетно-бесконечными и для общего исследования вычислимости могут рассматриваться как множества целых неотрицательных чисел.

Действительно, элементы A и B можно рассматривать как семейства двоичных записей, представляющих целые неотрицательные числа. В таких числах допускаются незначащие нули.

Поэтому функция f_P, вычисляемая произвольной программой P,  это числовая функция f_P: N^k  N.

То есть здесь будет принято считать, что начальные данные всякой программы представляют собой числовые наборы некоторой длины.

Результат работы программы также представляет некоторое целое неотрицательное число.

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