Шаг 5.
Понятие рекурсии.
Основные свойства примитивно рекурсивной функции

    На этом шаге мы рассмотрим основные свойства ПРФ.

Свойство 1.

Всякая примитивно рекурсивная функция f является всюду определенной функцией.

Доказательство.

Предположим, что функция есть ПРФ, следовательно, по определению примитивно рекурсивности функций, она имеет ПРО. Пусть последовательность функций b₁, ..., b_n - есть ее ПРО. Будем доказывать, что каждая функция этой последовательности является всюду определенной. Воспользуемся методом математической индукции.

1. Пусть n=1, тогда из определения ПРО следует, что b₁ является элементарной функцией, следовательно, она всюду определена.
2. Предположим, что для некоторого i<n, все функции b_k, i<=k<=i являются всюду определенными.
3. Докажем, что b_k+1 всюду определена. В этом случае функция b_k+1 является либо элементарной функцией, либо получается из предшествующих ей функций в этой последовательности с помощью одной из операций подстановки или примитивной рекурсии. По предположению индукции все функции последовательности b₁, ..., b_k являются всюду определенными и операции подстановки и примитивной рекурсии сохраняют свойство всюду определенности, следовательно b_k+1 - всюду определенная функция. Таким образом, метод математический индукции позволяет сделать вывод, что все функции из последовательности составляют ПРО функции , следовательно, всюду определенная функция. Что и требовалось доказать.

Свойство 2.

Если функция f получена из примитивно рекурсивных функций с применением операций подстановки или примитивной рекурсии, то она является ПРФ.

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

    Так как, f(x,y) = x + y является ПРФ, то получаемая функция тоже является ПРФ.

Свойство 3.

Всякая ПРФ является алгоритмически вычислимой.

Доказательство.

Это свойство доказывается так же, как и первое свойство ПРФ. Действительно, поскольку все элементарные функции алгоритмически вычислимы и операции подстановки и примитивной рекурсии сохраняют свойство алгоритмической вычислимости функций, то все функции, составляющие ПРО для примитивной рекурсивной функции f, являются алгоритмически вычислимыми, следовательно, f - алгоритмически вычислимая функция.

    На следующем шаге мы рассмотрим примитивно рекурсивные функции относительно совокупности функций.

Предыдущий шаг Содержание Следующий шаг