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

Очевидно, что вычислимыми являются все натуральные константы. Как и в формальной арифметике натуральных чисел, определим их с помощью константы 0 и функции следования.

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

.

Мощным средством построения новых функций является их суперпозиция.

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

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

Оператор примитивной рекурсии определяет n +1-местную функцию f через n -местную функцию g и n +2-местную функцию h.

Определение. Система равенств

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

Если , то . Например, так определяется хорошо знакомая функция факториал.

Здесь .

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

Дата добавления: 2014-01-20