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

В дальнейшем под множеством натуральных чисел 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 – функция следования.

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