Математическая логика и теория алгоритмов

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 выполнены соотношения:
       

Предложение (свойства операций суперпозиции и примитивной рекурсии). Операции суперпозиции и примитивной рекурсии сохраняют:

  1. всюду определённость функций;
  2. интуитивную вычислимость функций.
Доказательство проведем для операции суперпозиции. Пусть m-арная функция получена в результате операции суперпозиции из функций f и .
  1. Если все функции и f – всюду определённые, то функция g всюду определена. Функция g будет не всюду определённой, если одна из функций не всюду определена или если можно найти такие a1,...,am, что , но значение f(b1,...,bn) не определено.
  2. Если каким-либо образом можно вычислять значения функций и f,то ясно,как можно вычислить значение функции g. Придадим переменным некоторые значения a1,...,am. Вычислим все f(a1,...,am), 1 ≤ i ≤ n. Получим значения . Вычисляя теперь , получим,что g(a1,...,am)=c. Таким образом, если функции и f интуитивно вычислимы, то и функция g интуитивно вычислима.
       Предложение доказано.

       Функция f называется примитивно рекурсивной (п.р.ф.), если ее можно получить из простейших функций с помощью конечного числа операций суперпозиции и примитивной рекурсии.
Свойства примитивно рекурсивных функций характеризует следующее:

  1. Всякая примитивно рекурсивная функция всюду определена.
  2. Если функция f получена из примитивно рекурсивных функций с применением операций суперпозиции или примитивной рекурсии, то функция f является примитивно рекурсивной функцией.
  3. Все примитивно рекурсивные функции интуитивно вычислимы.
       Рассмотрим несколько примеров примитивно рекурсивных функций.

Пример 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 примитивно рекурсивная, то по предыдущей теореме функция также является примитивно рекурсивной.

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


назад | оглавление | вперёд