Математическая логика и теория алгоритмов
|
2.5 Примитивно рекурсивные функции |
назад | оглавление | вперёд |
       Часто решение поставленной задачи можно свести к вычислению некоторой целочисленной функции, определенной на множестве натуральных чисел. Этот раздел посвящен уточнению понятия алгоритма – классу частично рекурсивных функций. Этот подход к формализации алгоритма был разработан в 30-х годах прошлого столетия математиками К. Гёделем, С.К. Клини, А. Черчем.
       Будем рассматривать n-арные функции на множестве наборов натуральных чисел . Такие функции назовем арифметическими функциями. Если функция определена не для каждого набора натуральных чисел, то такие функции будем называть частично определенными арифметическими функциями(ч.а.ф).
       Основная идея состоит в том, чтобы получить все вычислимые функции из существенно ограниченного множества базисных функций с помощью простейших алгоритмических средств. Базисные функции выбираются так, чтобы их вычислимость была достаточно очевидна.
       Определим класс функций, следующим образом. Выделим конечное множество базовых функций и операции над ними для получения новых функций. В качестве базовых (простейших) функций берут следующие функции:
       Определим операции над функциями. Пусть имеются n- арная функция f и m-арные функции . Говорят, что m-арная функция
получена в результате операции суперпозиции или подстановки из функций f и
, если для любых
.
       Пусть заданы произвольные функции: n-арная функция g и n+2-арная функция h. Говорят, что n+1-арная функция f получена операцией примитивной рекурсии из функций g и h, если для любых выполнены соотношения:
       
       В случае если n=0, то определение имеет такой вид. Говорят, что функция f(x) получена операцией примитивной рекурсии из функции h(x,y) и константы С, если для любого x ∈ N выполнены соотношения:
       
Предложение (свойства операций суперпозиции и примитивной рекурсии). Операции суперпозиции и примитивной рекурсии сохраняют:
Доказательство проведем для операции суперпозиции. Пусть m-арная функция получена в результате операции суперпозиции из функций f и
.
       Функция f называется примитивно рекурсивной (п.р.ф.), если ее можно получить из простейших функций с помощью конечного числа операций суперпозиции и примитивной рекурсии.
Свойства примитивно рекурсивных функций характеризует следующее:
       Рассмотрим несколько примеров примитивно рекурсивных функций.
Пример 1.Рассмотрим функцию g(x1,...,xm)=1 для любых . Эта функция может быть получена суперпозицией из простейших функций.
       .
       Таким образом, функция является примитивно рекурсивной.
Пример 2.Покажем, что функция суммы f(x,y)=x+y примитивно рекурсивна. Действительно,
       ,
       где . Поскольку функции g и h являются примитивно рекурсивными, то и функция f является примитивно рекурсивной.
Пример 3.Покажем, что p(x,y)=x*y примитивно рекурсивна. Действительно, функция получена при помощи операции примитивной рекурсии
       ,
       где . Поскольку функции g и h являются примитивно рекурсивными, то и функция f является примитивно рекурсивной.
Пример 4.Покажем, что функция является примитивно рекурсивной.
       Представим функцию в виде примитивной рекурсии.
       ,
       где .
Пример 5.Покажем, что функция является примитивно рекурсивной.
       Представим функцию в виде примитивной рекурсии:
       .
Пример 6.Покажем, что функция является примитивно рекурсивной.
       Представим функцию в виде примитивной рекурсии:
       .
Пример 7.Покажем, что r(x)=|x-5| является примитивно рекурсивной.
       Действительно, функция получена суперпозицией функций .
Пример 8.Покажем, что функция является примитивно рекурсивной.
       Представим функцию f(x) в виде суммы (сумма является примитивно рекурсивной функцией) функций f1(x), f2(x), f3(x), где
       .
       Теперь покажем, что каждая из функций f1(x), f2(x), f3(x) является примитивно рекурсивной, поскольку представляет собой суперпозицию примитивно рекурсивных функций.
       .
Теорема.Пусть n-арная функция g примитивно рекурсивна. Тогда функции f, u, определенные следующим образом, также примитивно рекурсивны.
       .
Доказательство.Из условия теоремы следует, что
       .
       Следовательно, функция f строится с помощью примитивной рекурсии из примитивно рекурсивных функций g(x1,...,xn-1,0) и . Поэтому функция f примитивно рекурсивна. Для функции u доказательство аналогичное.
       Теорема доказана.
Пример.Положим g(x)=x. Тогда . Поскольку функция g(x)=x примитивно рекурсивная, то по предыдущей теореме функция
также является примитивно рекурсивной.
Теорема.
Доказательство.Докажем первое утверждение. Новая функция представима в виде суперпозиции п.р.ф.
       
       Остальные утверждения доказываются аналогично.
       Теорема доказана.