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

Напомним, что в этой главе множество натуральных чисел содержит 0, т.е. Будем рассматривать функции (возможно, частичные) Таким образом, если , то либо , либо не определено.

о s I

Эти функции могут быть вычислены с помощью соответствующего механического устройства (например, на машине Тьюринга). Определим операторы, которые по одной или нескольким заданным функциям строят новые функции.

Оператор суперпозиции. Пусть даны функция от переменных и функций от переменных.. Суперпозицией функций называется функция

Мы говорим, что функция получается применением оператора суперпозиции S к функциям и пишем S

Например, S(s,o) – это функция s(o т.е.

Оператор примитивной рекурсии. Пусть даны функции и Построим функцию Пусть зафиксированы значения Тогда полагаем:

Эти равенства определяют функцию однозначно. Функция называется функцией, полученной с помощью оператора R примитивной рекурсии. Используется запись R

Индуктивное определение функции (продемонстрированное в операторе примитивной рекурсии) в математике не редкость. Например, индуктивно определяются степень с натуральным показателем: факториал: и т.д.

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

Проверим, что функция является примитивно рекурсивной. Действительно, мы имеем: Это есть схема примитивной рекурсии, так как I а sSs, Здесь I а sS(s, I

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

Отметим, что примитивно рекурсивные функции всюду определены (т.е. определены для всех значений их аргументов). Действительно, простейшие функции o, s, I являются всюду определёнными, а применение операторов суперпозиции и примитивной рекурсии ко всюду определённым функциям даёт также всюду определённые функции.

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

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

Существенно более широким классом функций, чем примитивно рекурсивные функции, является класс рекурсивных функций (определение см. ниже). В литературе эти функции называют также частично рекурсивными. Для их определения введём ещё один оператор.

Оператор минимизации. Пусть дана функция Зафиксируем какие-либо значения первых переменных и будем вычислять и т.д. Если наименьшее натуральное число, для которого (т.е.

Если такого нет, то считаем, что не определено. Итак, возможны три случая:

1. существуют и не равны а

2. существуют и не равны а не существует;

3. существуют при всех и отличны от

Если имеет место 1-й случай, то а если 2-й или 3-й, то не определено. Про функцию полученную таким образом, говорят, что она получена из применением оператора минимизации М.

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

Функции, которые могут быть получены из простейших о s I применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.

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

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

Рекурсивные функции отражают наше интуитивное представление о функциях, вычислимых некоторым механическим устройством. В частности, они вычислимы на машинах Тьюринга (см. предыдущий раздел). Наоборот, всякая функция, вычислимая на машине Тьюринга, рекурсивна. Мы не будем проверять этот факт, так как это потребовало бы слишком много времени и места. Полное доказательство можно найти, например, в книге А.И.Мальцева “Алгоритмы и рекурсивные функции”. В предыдущем разделе, впрочем, были построены машины Тьюринга, реализующие функции o s I С другой стороны, не всякая функция натуральных аргументов является рекурсивной, даже не всякая функция одного аргумента. В самом деле, рекурсивных функций имеется лишь счётное число (т.е. их можно занумеровать натуральными числами), а все функции образуют несчётное множество. Существование нерекурсивных функций и является “математической причиной” наличия алгоритмически неразрешимых задач (о них см. следующий раздел). Примеры решения задач

Пример 1. Доказать, что следующие функции примитивно рекурсивны: а) б) в) (функция “сигнум”).

Решение. а) Имеем: о Это схема примитивной рекурсии. Так как функция примитивно рекурсивна, то функция тоже.

б) Схема примитивной рекурсии для функции выглядит так: s(o Так как функция примитивно рекурсивна, то тоже.

в) Имеем: Следовательно, функция примитивно рекурсивна.

Пример 2. Доказать, что функция

рекурсивна.

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

Известно, что функция примитивно рекурсивна (см. предыдущее упражнение). Следовательно, функция рекурсивна. Это влечёт рекурсивность функции а она совпадает с функцией

3. Выяснить, что из себя представляет функция М где функция “сигнум” (см. предыдущую задачу).

Решение. Пусть М Тогда Поэтому а остальные значения функции не определены. Задачи для самостоятельного решения

1. Доказать, что следующие функции примитивно рекурсивны:

а) б) в)

в)

2. Доказать, что функция является рекурсивной.

3. Доказать, что если функция примитивно рекурсивна, то функция – тоже. Используя это утверждение и результат задачи 1в), доказать примитивную рекурсивность функции

Ответы

1. Указание. а) б)

2. Указание.

3. Указание: