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

Простейшими эффективно вычислимыми функциями принято считать следующие три числовые функции:

1) ;

2) ;

3) .

Иногда данные функции называют соответственно: оператор сдвига, оператор аннулирования и оператор проектирования. Все эти три функции всюду определены и интуитивно вычислимы.

Для построения частично-рекурсивных функций вводится три основных операции над простейшими функциями. Рассмотрим каждую из них.

1. Операция суперпозиции функций (составление из двух и более функций одной сложной функции, или, то же самое, что подстановка функции в функцию).

Пусть даны функции и . Рассмотрим функцию , определяемую равенством

Говорят, что функция получена из функций и их суперпозицией.

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

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

.

Так как простейшие функции являются всюду определенными и интуитивно вычислимыми, то, очевидно, функции и тоже будут всюду определенными интуитивно вычислимыми.

2. Операция (схема) примитивной рекурсии. Центральное место в построении частично-рекурсивных функций занимает операция, или так называемая схема примитивной рекурсии (СПР). Она задается следующим образом. Пусть имеются две функции и . Из этих функций составим новую функцию, удовлетворяющую следующим равенствам:

(1)

Нетрудно заметить, что функция зависит от аргумента, функция − от аргументов, а функция – от аргумента. Говорят, что если функция получена из функций и и удовлетворяет системе равенств (1), то она получена по схеме примитивной рекурсии.

Очевидно, что если функции и интуитивно вычислимы, то интуитивно вычислимой будет и функция . Действительно, пусть . Тогда последовательно находим

;

;

и т.д. Тем самым рекурсивно получаем значения функции .

В частности, если функция зависит только от двух аргументов, т.е. имеет вид , то СПР будет иметь вид

(2)

Если же функция зависит всего лишь от одного аргумента, то СПР будет иметь вид

, (3)

где a – любое постоянное число.

Ранее мы уже определили частично-рекурсивную функцию как функцию, которая получается за конечное число шагов из простейших функций , и с помощью операции суперпозиции, СПР и операции минимизации. Если же функция получается из тех же простейших функций, и с помощью только операции суперпозиции и СПР (т.е. без применения операции минимизации, рассмотрение которой нам еще предстоит), то такую функцию называют примитивно рекурсивной. Операция суперпозиции и СПР, примененные ко всюду определенным функциям, дают снова всюду определенные функции. Поэтому все примитивно-рекурсивные функции всюду определены.

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

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

Пример. 1. Пусть функция задана равенствами [перемена мест аргументов в обозначении функции роли не играет, поэтому можем писать как , так и ]:

(4)

Очевидно, что в этой системе равенств Но второе равенство системы (4) еще не дает основания считать, что система этих двух равенств представляет СПР, поскольку по определению правая часть второго равенства должна зависеть от трех (в данном случае) аргументов. Поэтому левую часть второго равенства, зависящую от двух аргументов , приведем к виду, зависящему от трех аргументов , т.е. нам надо получить в явном виде.

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

Таким образом, исходную функцию заданную двумя равенствами, мы свели к СПР, заданной также двумя равенствами:

(5)

Вычислим при , используя полученную СПР соответствующее число раз (фактически используя алгоритм в строгом смысле его понимания).

Из первого равенства системы (5), изменяя x от 0 до 2, получим

Из второго равенства системы (5) и из того, что последовательно можно записать:

Представляет интерес вопрос определения аналитического вида функции соответствующей СПР (5). Для этого воспользуемся сначала вторым равенством системы (5) и последовательно запишем

.

Проделав эту операцию раз, мы придем в конце концов к выражению . Но учитывая первое равенство системы (4) , окончательно будем иметь . Отсюда видим, что обычную операцию сложения можно свести к алгоритмическому процессу (к схеме примитивной рекурсии) вычисления суммы двух чисел. Действительно, используя СПР в рассматриваемом примере, мы получили . То же самое мы получим из аналитического выражения при тех же численных значениях аргументов .

3. Операция минимизации (μ-оператор). Пусть дана некоторая функция . Зафиксируем значение и найдем значение , при котором . В частном случае может . Сложнее решается задача отыскания для данной функции и фиксированного наименьшего из тех значений при котором . Очевидно, что результат решения задачи зависит от поэтому наименьшее значение y, при котором , есть функция от x, т.е. . Эту функцию принято обозначать , и при этом говорят, что для перехода от функции к функции применяется μ -оператор. Читается эта запись так: “наименьшее y такое, что ”.

Для функции переменных μ - оператор определяется аналогично

.

Получать функцию из функции путем применения μ -оператора можно по следующему алгоритму.

1. Вычислим . Если , то полагаем . Если , то увеличиваем на 1 и переходим к следующему шагу.

2. Вычислим . Если , то полагаем . Если же , то увеличиваем на 1 и переходим к шагу 2.

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

Пример 2. Функцию представим с помощью μ -оператора: . Пользуясь представлением функции в виде μ -оператора, вычислим, например, ее значение при , т.е. найдем то значение при котором . Для этого, зафиксировав , будем последовательно изменять значения :

Таким образом,