Частично рекурсивные функции

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

8.2.1. Простейшие функции

Следующие функции называются простейшими:

тождественный ноль О (x) = 0;

функция следования S (x) = x + 1;

функции проекции (x ₁,..., x_n), где 1 m n.

Все эти функции являются вычислимыми, поскольку могут вычисляться с помощью очевидных алгоритмов.

8.2.2. Элементарные функции

Пусть заданы функции:

f (x ₁,..., x _k), g_i (x_{i 1},..., x_{im i}), i = 1,..., k.

Функция h (x_{j 1},..., x_{j r}) получается из заданных функций с помощью операции суперпозиции, если её можно представить в виде выражения:

f (g ₁(x _1,1,..., x _{1, m 1}),..., g _k(x _k,1,..., x _{k, m k})).

Здесь переменными функции h являются все различные переменные функций g_i (x_{i, 1},..., x_{i , mi}), i = 1,..., k.

Если все функции f (x ₁,..., x_n), g_i (x_{i 1},..., x_imi), i = 1,..., k, являются вычислимыми, то вычислима и суперпозиция таких функций - функция h.

Дата добавления: 2015-03-31