Рекуррентные функции

В дальнейшем под множеством натуральных чисел N будем понимать множество N = {0,1,2,…,k,…}

Пусть y = f(x₁, x₂,…, x_n) – функция от n переменных. Обозначим D(y) – область определения функции y = f(x₁, x₂,…, x_n), E(y) – область значений функции y = f(x₁, x₂,…, x_n).

Функция y = f(x₁, x₂,…, x_n) называется числовой функцией, если:

1) D(y)=N ×∙ N ∙× …×∙ N = ;

2) E(y) N

Функция y = f(x₁, x₂,…, x_n) называется частично числовой функцией, если:

1) D(y) N ×∙ N∙×…×∙N = ;

2) E(y) N.

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

1) O(x) = 0 – нуль-функция

2) (x₁, x₂,…, x_n) = x_m , 1 ≤ m ≤ n – функция повторяющая значение своих аргументов;

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

Определим следующие три операции: суперпозиции, примитивной рекурсии и минимизации.