Договоримся, что:
1. множество N натуральных чисел содержит 0 (нуль), т.е. N={0,1,2,3,…};
2. рассматриваемые функции f=f(x1,x2,…,xn) определены только тогда, когда переменные принимают значения из N, т.е. xi∈N;
3. область значений функций D⊆N;
4. рассматриваемые функции f=f(x1,x2,…,xn) могут быть частично определенные, т.е. определенные не для всех наборов натуральных чисел.
Введём в рассмотрение простейшие функции:
o(x)=0, s(x)=x+1, Inm(x1,…,xn)=xm
Эти функции могут быть вычислены с помощью соответствующего механического устройства (например, на машине Тьюринга). Определим операторы, которые по одной или нескольким заданным функциям строят новые функции.
Оператор суперпозиции. Пусть даны функция f(x1,x2,…,xk) от k переменных и k функций f1(x1,x2,…,xn),…,fk(x1,x2,…,xn) от n переменных. Суперпозицией функций f,f1,…,fk называется функция:
φ(x1,x2,…,xn)= f(f1(x1,x2,…,xn),…,fk(x1,x2,…,xn))
Мы говорим, что функция φ получается применением оператора суперпозиции Sk+1 к функциям f,f1,…,fk, и пишем φ=Sk+1(f,f1,…,fk). Например, S2(s,o)=s(o(x)), т.е. функция, тождественно равная 1, а S2(s,s)=s(s(x)) — это функция у(x)=x+2.
Оператор примитивной рекурсии. Пусть даны функции g(x1,x2,…,xn) и h(x1,x2,…,xn+2). Построим функцию f(x1,x2,…,xn+1) Пусть зафиксированы значения x1,x2,…,xn. Тогда полагаем:
f(x1,x2,…,xn,0)=g(x1,x2,…,xn)
f1(x1,x2,…,xn,y+1)= h(x1,x2,…,xn,y,f(x1,x2,…,xn,y))
Эти равенства определяют функцию f(x1,x2,…,xn+1) однозначно. Функция f называется функцией, полученной с помощью оператора R примитивной рекурсии. Используется запись f=R(g,h).
Индуктивное определение функции (продемонстрированное в операторе примитивной рекурсии) в математике не редкость. Например, индуктивно определяются:
1) степень с натуральным показателем: a0=1, an+1=an·a;
2) факториал: 0!=1, (n+1)!=n!·(n+1) и т.д.
Определение.Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, Inm(x1,…,xn)=xm применением конечного числа раз операторов суперпозиции и примитивной рекурсии, называются примитивно рекурсивными.
Проверим, что функция u(x,y)=x+y является примитивно рекурсивной. Действительно, мы имеем: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Это есть схема примитивной рекурсии, так как x11(x), а u(x,y)+1=s(u(x,y))=S2(s,u). Здесь g(x)=x12, а h(x,y,u)=s(u)=S2(s,I33).
Аналогично доказывается, что функции m(x,y)=x·y, d(x,y)=xy (считаем по определению 00=1), fact(x)=x! и многие другие являются примитивно рекурсивными.
Отметим; что примитивно рекурсивные функции всюду определены (т.е. определены для всех значений их аргументов). Действительно, простейшие функции o, s, Inm являются всюду определёнными, а применение операторов суперпозиции и примитивной рекурсии ко всюду определённым функциям даёт также всюду определённые функции. Значит, такая функция, как
| f(x,y) = { | x-y, если x≥y |
| не существует, если x<y |
примитивно рекурсивной быть не может. Рассматривать функцию f(x,y)=x-y здесь мы не имеем права, так как значения функций должны быть натуральными числами (поэтому не отрицательными). Однако, можно рассмотреть функцию
| x÷y = { | x-y, если x≥y |
| 0, если x<y |
Проверим, что она примитивно рекурсивна. Докажем вначале, что функция φ(x)=x÷1 примитивно рекурсивна. Действительно, φ(0)=0. φ(y+1)=(y+1)÷1=y, что служит схемой примитивной рекурсии для функции x÷1. Наконец, x÷0=x, x÷(y+1)=(x÷y)÷1=φ(x÷y) ? схема примитивной рекурсии для x÷y.
Существенно более широким классом функций, чем примитивно рекурсивные функции, является класс рекурсивных функций (определение см. ниже). В литературе эти функции называют также частично рекурсивными. Для их определения введём ещё один оператор.
Оператор минимизации. Пусть дана функция f(x1,x2,… ,xn,xn+1). Зафиксируем какие-либо значения x1,x2,…,xn первых n переменных и будем вычислять f(x1,x2,…,xn,0), f(x1,x2,…,xn,1), f(x1,x2,…,xn,2) и т.д. Если y ? наименьшее натуральное число, для которого f(x1,x2,…,xn,y)=xn+1 (т.е. значения f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x1,x2,…,xn,y-1) все существуют и не равны xn+1), то полагаем g(x1,x2,…,xn,xn+1)=y. Таким образом, g(x1,x2,…,xn,xn+1)=min(y|f(x1,x2,…,xn,y)=xn+1).
Если такого y нет, то считаем, что f(x1,x2,…,xn,xn+1) не определено. Итак, возможны три случая:
1. f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x1,x2,…,xn,y-1) существуют и не равны xn+1, а f(x1,x2,…,xn,y)=xn+1;
2. f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x1,x2,…,xn,y-1) существуют и не равны xn+1, а f(x1,x2,…,xn,y) не существует;
3. f(x1,x2,…,xn,i) существуют при всех i∈N и отличны от xn+1.
Если имеет место 1-й случай, то g(x1,x2,…,xn,xn+1)=y, а если 2-й или 3-й, то g(x1,x2,…,xn,xn+1) не определено. Про функцию g полученную таким образом, говорят, что она получена из f применением оператора минимизации М. Мы пишем g=Мf.
Оператор минимизации — это очевидное обобщение оператора взятия обратной функции. Обобщение довольно глубокое, так как от функции f не требуется, чтобы она была взаимно однозначной (по переменной xn+1).
Определение. Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, Inm(x1,…,xn)=x применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.
Класс рекурсивных функций шире класса примитивно рекурсивных функций хотя бы по тому, что он содержит не только всюду определённые функции. Докажем, например, что функция
| f(x,y) = { | x-y, если x≥y |
| не существует, если x<y |
является рекурсивной. Действительно, f(x,y)=min(z|y+z=x), а ранее было установлено, что функция u(x,y)=x+y примитивно рекурсивна.
Рекурсивные функции отражают наше интуитивное представление о функциях, вычислимых некоторым механическим устройством. В частности, они вычислимы на машинах Тьюринга. Наоборот, всякая функция, вычислимая на машине Тьюринга является рекурсивной. Мы не будем проверять этот факт, так как это потребовало бы слишком много времени и места.
Отметим, что не всякая функция натуральных аргументов является рекурсивной, даже не всякая функция одного аргумента. Существование нерекурсивных функций и является «математической причиной» наличия алгоритмически неразрешимых задач.