Рассмотрим два каких-либо множества X={x₁, x₂, ...}, Y={y₁, у₂, …}. Если некоторым элементам множества Х поставлены в соот­ветствие однозначно определенные элементы множества Y, то говорят, -что задана одноместная частичная функция из Х в Y. Совокупность элементов множества X, у кото­рых есть соответствующие элементы в Y, называется областью определенности функции, а совокупность эле­ментов Y, которые соответствуют элементам множества X, называется совокупностью значений функции. Если область определенности совпадает- с множеством X, называемым областью определения функции, то функция называется всюду определенной, или просто функцией.

Если функция f ставит в соответствие элементу x_i Î Х элемент y_i Î Y, то у_i, называется значением функции f в точке x_i: Вообще х называется независимой переменной, у - зависимой переменной. Функция называется взаимно-однозначной, или одно-однозначной, если она разным эле­ментам множества Х ставит в соответствие разные эле­менты множества Y, т. е. если из неравенства x_i ¹ x_j следует неравенство y_i ¹ y_j. Функции f и g из Х в Y называются равными, если они имеют одну и ту же область определенности и значения их совпадают в каждой точке области определенности.

Частичная функция⁸ из X₁ ´ X₂ ´ … ´ X_n, где X₁ ´ X₂ ´ … ´ X_n – декартово произведение множеств X₁, X₂, …, X_n, в Y называется частичной функцией от n переменных, или n-местной частичной функцией из X₁ ´ X₂ ´ … ´ X_n в Y.

В дальнейшем будем обозначать множество всех натуральных чисел через N. Частичная функция из N^(k) в N называется k-местной числовой частичной функцией. Здесь

N^(k)=N ´ N ´…´ N

                                      _k

обозначает декартову k-ую степень множества N.

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

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

функция-константа C_aⁿ(x₁,…, x_n)=a

 функция тождества I_mⁿ(x₁,…, x_n)=x_m (1mn, n=1, 2,…).

Преобразования функций называются операторами. Рассмотрим основные операторы, используемые при построении частично-рекурсивных функций⁹.

Оператор подстановки 

Пусть задано п каких-либо m-местных частичных функций f₁,… , f_n из А в В и пусть задана частичная n-местная функция f из В в С. Введем частичную функцию g из А в С такую, что

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

для любых x₁, …,x_m из A.

Преобразование, с помощью которого получена функ­ция g из f, f₁, f₂, …, f_n, называется оператором подстановки или суперпозиции, и обозначается символом S⁽ⁿ⁺¹⁾, где (n+1) - число функций.

Оператор подстановки определен для функций f₁, … , f_n с одинаковым числом переменных. Затруднение, возникаю­щее при необходимости подстановки функций с разным числом переменных, можно преодолеть путем введения с помощью функции тождества фиктивных переменных. Например, функцию двух переменных j(x₁, x₂) можно представить в виде функции трех переменных, из которых одна является фиктивной:

j(x₁, x₂)= y(x₁, x₂, x₃)= j(I³₁(x₁, x₂, x₃), I³₂(x₁, x₂, x₃)).

Обозначим через Fⁿ множество всех частичных⁸ n-мест­ных числовых функций. Оператор S⁽ⁿ⁺¹⁾ является всюду определенной (n+1)-местной функцией из Fⁿ ´ F^m ´ … ´ F^m  в F^m. Если обозначить через F множество всех частичных числовых функций от произвольного числа переменных, то оператор S⁽ⁿ⁺¹⁾ можно рассматривать как частичную (n+1)-местную функцию из F⁽ⁿ⁺¹⁾ в F.

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

Пусть заданы какие-либо числовые частичные функции: n-местная g и (n+2)-местная h; (n+1)-местная частичная функция f  возникает из функции g и h с помощью оператора примитивной рекурсии (или просто примитивной рекурсии), если для натуральных значений x₁, …, x_n, y

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)).

Оператор примитивной рекурсии обозначают через R:

f = R(g, h).

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

f(x₁, …, x_n, 1) = h(x₁, …, x_n, 0, g(x₁, …, x_n, y)),

· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·

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

Совокупность этих равенств для любых функций g и h однозначно определяет значения функции f. Таким образом, для каждых двух частичных числовых функций g от n переменных и h от (п +2) переменных существует одна и только одна функция f от (n+1) переменной, возникаю­щая примитивной рекурсией (по данной переменной x_n+1).

Если для некоторых систем чисел x₁, …, x_n, y₁ зна­чение f неопределенное, то неопределенными будут и зна­чения f (x₁, …, x_n, у) для всех у > y₁. Если функции g и h всюду определенные, то и f =R{g, h) - всюду определенная функция.

Рассмотрим примеры функций, возникающих с помощью опера­тора примитивной рекурсии.

Пример 1. Пусть g=0, h = 2x+y, тогда

f(0)=0,

f(1)=0,

f(2)=2,

f(3)=22+2=6

f(4)=23+22+2=12,

f(x+1)=2x+2(x-1)+…+22+2=2,

т.е. функция f(x+1) = x(x+1) возникает примитивной рекурсией из постоянной g=0 и функции h=2x+y.

При задании номера переменной, по которой осущест­вляется рекурсия, функция f однозначно определяется видом функций g и h; переход к рекурсии по другой пере­менной в общем случае приводит к изменению функции f.

Пример 2. Если g=0, h=x+2y, то

        f(0)=0,

        f(1)=0,

        f(2)=1,

        f(3)=2+21=4,

        f(4)=3+22+2²1=11,

        f(5)=4+23+2²2+2³1=26,

        f(x+1)=x+2(x-1)+2²(x-2)+…+2^x-22+2^x-11=, x1

- это арифметико-геометрическая прогрессия, сумма которой

;

поэтому

f(x+1) = 2^x+2-x-2.

Эта функция возникает примитивной рекурсией из постоянной g=0 и функции h=y+2x.

Пример 3. Пусть g=0, h=x-2y, тогда

f(0)=0,                  f(3)=2-2·1=0,

f(1)=0,                  f(4)=3,

f(2)=1,                  f(5)=4-2·3 -не определено;

следовательно, значения функции f(x) для x³5 не определенны.

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

Рассмотрим какую-нибудь n-местную (n ³1) частичную⁸ числовую функцию f. Допустим, что существует алгоритм для вычисления значений функции f во всей области определенности. Зафиксируем значения x_{i, …,} x_n-1 пер­вых (п—1) аргументов f и рассмотрим уравнение

f(x₁, ..., x_n-1, у)=x_п.

Для того чтобы найти целочисленное решение у этого уравнения, будем по имеющемуся алгоритму вычислять значения f(x₁, ..., x_n-1, у) последовательно для у=0, 1, 2, .... Найденное в процессе такого вычисления наи­меньшее значение а, для которого

f(x₁, ..., x_n-1, a)=x_п,

обозначим через

m _y(f(x₁, ..., x_n-1, y)=x_п).

Данный процесс нахождения а не дает результата в тех случаях, когда

1) значение f(x₁, ..., x_n-1, 0) не определено;

2) значения f(x₁, ..., x_n-1, у) при у=0, 1, ..., k опре­делены, но отличны от x_n, а значение f(x₁, ..., x_n-1, k+1) не определено;

3) значения f(x₁, ..., x_n-1, у) определены для всех у=0, 1, 2, ..., но отличны от x_n.

В этих случаях значение m _y считается неопределенным; m _y является частичной функцией от п переменных x₁, ..., x_n. Эту функцию будем обозначать через Mf. Здесь М — символ оператора минимизации, преобразующего функцию f в Mf.

Пример 4. Пусть f(у)=2^y, тогда Mf(x)= m _y(2^y=х). функ­ция Мf(x) определена для значений х, равных 2ⁿ, где n=0, 1, 2, ... , в этих случаях Mf(x)=Log₂x=n. В частности,

Mf(1)=0,

Mf(2)=1;

значения функции Mf при x=0 и x=3 не определены.

Пример 5. Пусть f(x, у)=у—х, тогда Мf(х,z)= m _y(у—х=z). Значение этого выражения неопределенное, так как уже при у=0 (x>0) функция f(x, у)=у—х не определена. Но с другой стороны, уравнение у—х=z имеет решение у=z+х.

Пример 5 показывает, что значение функции Мf не является в общем случае решением уравнения f(x₁, ..., x_n-1, у)=x_п. Значение Мf совпадает с минимальным решением уравнения f(x₁, ..., x_n-1, у)=x_п, если функция f(x₁, ..., x_n-1, у) для данного набора значений x₁, ..., x_n-1 определена при всех y £Mf(x₁, …, x_n).

Если функция f одноместная, то функция Мf назы­вается обращением функции f, или обратной функцией; ее обозначают часто через f^--1:

f^--1(x)= m _y(f(y)=x).