В дальнейшем под множеством натуральных чисел N будем понимать множество N={0,1,2,…,k,…}
Пусть y= f(x1, x2,…, xn) – функция от n переменных. Обозначим D(y) –
область определения функции y= f(x1, x2,…, xn) E(y) – область значений
функции y= f(x1, x2,…, xn)
Функция y=f(x1, x2,…, xn) называется числовой функцией, если:
1) D(y)=N ×∙ N ∙× …×∙ N = ;
2) E(y) N
Функция y=f(x1, x2,…, xn) называется частично числовой функцией, если: 1) D(y) N ×∙ N∙×…×∙N = ;
2) E(y) N.
Следующие числовые функции мы будем называть простейшими:
1) O(x)=0 – нуль-функция;
2) (x1, x2,…, xn)=xm, 1≤ m≤ n – функция повторяющая значение своих аргументов;
3) S(x)=x+1 – функция следования.
Определим следующие три операции: суперпозиции, примитивной рекурсии и минимизации.