Под числовыми функциями мы понимаем функции f:Nⁿ®N, где N=w – множество всех натуральных чисел x³0, Nⁿ={(x₁,…,x_n):x₁ÎN,…,x_nÎN} – его декартова степень. Эти функции называются n-местными. Функцией N⁰®N, зависящей от 0 переменных, называется произвольная константа cÎN.  Частичной (числовой) n-местной функцией называется функция f: D®N, определенная на некотором подмножестве DÍNⁿ декартовой степени. Обозначим D через Dom(f) и будем называть её областью определения частичной функции f. Для частичной n-местной функции f будем применять обозначения f:Nⁿ®N.

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

Функции s:N®N, 0:N⁰®N  и  Iⁿ_m: Nⁿ®N, принимающие значения s(x) = x + 1, константа0 и Iⁿ_m(x₁,…,x_n) = x_m, для всех x, x₁,…,x_n Î N и n ³ m ³ 1, называются простейшими. Операции над функциями будут называться операторами.

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

Композиция частичных функций

Частичные функции f:A®B можно определить как функции, заданные на некоторых подмножествах Dom(f)ÍA и принимающие значения в B. Если Dom(f) = A, то f называется определенной всюду. В некоторых случаях частичные функции удобно рассматривать как определенные всюду. С этой целью к каждому множеству добавляется бесконечно удаленная (или отмеченная) точка *. Произвольная частичная функция f:A®B расширяется до функции :AÈ{*}®BÈ{*} по формулам (x) = f(x) для x Î Dom(f) и по формулам (x)=* для всех остальных x, включая *. С другой стороны, каждая функция :AÈ{*}®BÈ{*} определяет частичную функцию g:A®B, принимающую значения g(x) = (x) для x Î ^-1(B). Ясно, что область Dom(g) = ^-1(B) состоит из точек, не отображающихся в бесконечно удаленную. Соответствие, сопоставляющее частичным функциям f функции  является взаимно однозначным. Рассматривая частичные функций f как их расширения , легко определить композицию частичных функций f:A®B и g:B®C. Если f и g определены всюду, то композиция совпадает с обычной. В общем случае область определения композиции g×f состоит из точек xÎA, таких, что g(f(x)) ¹ *.

Пусть f₁,…,f_n:N^m®N – частичные функции. Определим частичную функцию (f₁,…,f_n):N^m®Nⁿ, полагая

(f₁,…,f_n)(x)=(f₁(x),…,f_n(x))

для всех xÎDom(f₁)Ç… ÇDom(f_n) ÍN^m.

Пусть f₁,…,f_n:N^m®N и g:Nⁿ®N – частичные функции. Оператор композиции (или суперпозиции) Sⁿ⁺¹ сопоставляет им частичную функцию:

Sⁿ⁺¹(g, f₁,…,f_n)=g°(f₁,…,f_n).

Областью определения частичной функции g°(f₁,…,f_n) является подмножество точек x = (x₁,…,x_m)ÎDom(f₁)Ç…ÇDom(f_n),  для которых (f₁(x),…,f_n(x))ÎDom(g).

Пример 1

Рассмотрим частичные функции g:N²®N,  f₁:N®N,  f₂:N®N, принимающие значения g(x₁,x₂) = x_{1 –} x₂, f₁(x) = x/2, f₂(x) = x/3. Функция f₁ определена для четных x;  f₂

для чисел, кратных 3; g(x₁,x₂) – для пар чисел x₁³x₂. Следовательно, Dom(g) = {(x₁,x₂):x₁³x₂}, Dom(f₁) = {2x:xÎN} = 2N, Dom(f₂) =3N. Оператор S³ сопоставляет этим частичным функциям композицию g°(f₁,f₂):N®N. Область  Dom(g°(f₁,f₂)) состоит из z Î 6N, удовлетворяющих неравенству z/2 ³ z/3. Поскольку это неравенство выполнено для всех z, то область равна 6N. Если поменять местами f₁ и f₂, то область определения композиции изменится. Она будет состоять из z Î 6N, удовлетворяющих z/3 ³ z/2. Следовательно, Dom(S³(g, f_2, f₁)) = {0}.

Оператор примитивной рекурсии

Пусть заданы частичные функции g:Nⁿ®N и h:Nⁿ⁺²®N. Оператором примитивной рекурсии называется оператор, сопоставляющий паре (g,h) такую частичную функцию f:Nⁿ⁺¹®N, что для всех x₁,…,x_n,у Î N имеют место равенства:

f(x₁,…,x_n,0) = g(x₁,…,x_n);

f(x₁,…,x_n,y+1) = h(x₁,…,x_n,y, f(x₁,…,x_n,y)).

Поскольку область определения и значения дополняются отмеченной точкой, то равенство частичных функций означает, что для каждого значения аргумента либо левая, либо правая части равенства определены и равны между собой, либо обе его части не определены. Значение оператора примитивной рекурсии  обозначается: f = R(g,h). Если g и h определены всюду, то f = R(g,h) определена всюду.

Если n = 0, то для любых числа g Î N и частичной функции h:N²®N частичная функция f = R(g,h) определяется с помощью равенств:

f(0) = g,   f(y + 1) = h(y,f(y)).

Функция f называется примитивно рекурсивной, если ее можно получить из простейших функций s, 0 и Iⁿ_m с помощью операторов композиции и примитивной рекурсии (таким образом, примитивно рекурсивная функция всюду определена.)

Пример 2

Функция o: N ® N, принимающая постоянные значения o(x)=0, будет примитивно рекурсивной в силу

o(0) = 0;

o(y+1)= I²₂(y, o(y)).

Функция оⁿ:Nⁿ®N, все значения которой равны нулю, примитивно рекурсивна, ибо она является композицией о°Iⁿ₁ простейших функций Iⁿ₁:Nⁿ®N и о:N®N. Рассмотрим при k ³ 1 функцию c_k:Nⁿ®N, все значения которой равны k. Функция c_k равна композиции функций оⁿ:Nⁿ®N и k функций N®N®…®N, каждая из которых равна s, c_k = s^k°oⁿ. Стало быть, c_k примитивно рекурсивна.

Пример 3

Функция f:N²®N, заданная как f(x,y) = x + y, удовлетворяет соотношениям:

f(x,0) = x;

f(x,y + 1)= (x + y) +1 =f(x,y) + 1 =s(f(x,y)).

Положим: g(x) = I¹₁(x) = x,  h(x,y,z) = s(z). Так как f(x,0) = g(x) и f(x,y + 1) = h(x,y,f(x,y)), то f = R(g,h) = R(I¹₁,s ° I³₃). Значит, f – примитивно рекурсивна.

Предложение 1 Для любых примитивно рекурсивных функций  f(x₁, …, x_n) и g(x₁, …, x_n) их сумма примитивно рекурсивна.

Доказательство. Вытекает из равенства

f(x₁, …, x_n)+g(x₁, …, x_n)= S(+,f,g) (x₁, …, x_n).

Пример 4

Функция f:N²®N, заданная как f(x,y) = x×y, удовлетворяет соотношениям:

f(x,0) = 0;

f(x,y + 1)= x ( y + 1) =f(x,y) + x.

Положим: g(x) = o(x),  h(x,y,z) = x+z . Так как f(x,0) = o(x) и f(x,y + 1) = h(x,y,f(x,y)), то f = R(g,h) = R(o, S(+, I³₁,, I³₃). Значит, f – примитивно рекурсивна.

Предложение 2 Для любых примитивно рекурсивных функций f(x1, …, xn) и g(x1, …, xn) их произведение примитивно рекурсивно.

Пример 5

Рассмотрим функцию: f(x,y) = x^y. Поскольку f(x,0) = 1, и f(x,y + 1) = x×f(x,y) = g(x,y,f(x,y)), где g(x,y,z) = x×z – примитивно рекурсивная функция (как композиция операции умножения и функции (I³₁, I³₃):N³®N²), то f(x,y) примитивно рекурсивна.

Пример 6

Пусть d(x) = max(0,x – 1). Имеют место равенства d(0) = 0 и d(y + 1) = y = g(y,d(y)), где g(y,z) = I²₁(y,z) =y. Следовательно, d(x) – примитивно рекурсивна.

Пример 7

Пусть r(x,y) = max(0,x – y). Верны соотношения r(x,0) = x иr(x,y + 1) = d(r(x,y)) = g(x,y,r(x,y)), где g(x,y,z) = d(z) – функция из примера 5. Значит, r(x,y) – примитивно рекурсивна.

Пример 6 показывает, что функция f(x,y)  =ôx-yô= r(x,y) + r(y,x) примитивно рекурсивна, как композиция функций x₁ + x₂  и пары функций (r(x,y),r(y,x)):N²®N² (примитивная рекурсивность функции r(y,x) получается из разложимости r(y,x) = S³(r, I²₂, I²₁)).

Оператор минимизации

Пусть g:Nⁿ⁺¹®N – частичная функция. Будем говорить, что частичная функция f:Nⁿ®N получается из неё с помощью оператора минимизации, и писать:

f(x₁,…,x_n) = my[g(x₁,…,x_n,y) = 0],

если выполнено следующее условие: f(x₁,…,x_n) определено и равно yÎN тогда и только тогда, когда значение g(x₁,…,x_n,0),…,g(x₁,…,x_n,y -1) определены и не равны 0, а g(x₁,…,x_n,y) = 0.

Частичная функция f:Nⁿ®N называется частично рекурсивной, если она может быть получена из простейших функций 0, s, Iⁿ_m за конечное число применений операторов композиции, примитивной рекурсии и минимизации.

Пример 8

Рассмотрим примитивно рекурсивную функцию: g(x,y) = x – Sg(y), где Sg(y) = 0, при y = 0, и Sg(y) = 1, для y > 0. Тогда значения:

f(x)=my[ôx-Sg(y)ô= 0]

не определены при x > 1. Наименьшее среди y Î N, удовлетворяющих 0 – Sg(y) = 0, будет равно 0, а наименьшее среди y, при которых 1 – Sg(y) =0, равно 1. Следовательно, f(0) = 0,  f(1) = 1, и f(x) не определены при x > 1. Функция ôx – Sg(y)ô примитивно рекурсивная, значит, f(x) – частично рекурсивная.

Пусть А – подмножество натуральных чисел. Частичной характеристической функцией множества А называется частичная функция C_A:N®N, равная 0 в точках множества А и не определенная вне А. Множество А называется частично рекурсивным, если его частичная характеристическая функция частично рекурсивна. Множество А называется примитивно рекурсивным, если функция N®N, равная 0 на А и равная 1 вне А, является примитивно рекурсивной.

Теорема. Пусть f:N®N – примитивно рекурсивная функция, A Í N – примитивно рекурсивное множество. Тогда частичная функция f_A:N®N, определенная как f_A(x) = f(x) для x Î A и неопределенная при x Ï A, является частично рекурсивной.

Доказательство. Легко видеть, что f_A(x) = f(x) + C_A(x). Поэтому f_A частично рекурсивна, как сумма  частично рекурсивных функций.

Понятие частично рекурсивной функции является одним из главных в теории алгоритмов. Частично рекурсивная функция вычислима с помощью процедуры, отвечающей нашему представлению об алгоритме. С другой стороны, все известные до сих пор уточнения определения алгоритма не привели к классу вычислимых функций, который был бы шире класса частично рекурсивных. Поэтому общепринятой является следующая гипотеза:

Тезис Чёрча. Класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.