Рекурсивные, частично рекурсивные функции

Мы будем рассматривать частичные арифметические функции fⁿ (x1,…,xn): Nⁿ -->N.

Здесь верхний индекс n у имени функции f обозначает число ее аргументов ("арность"). Бани арность ясна из контекста или несущественна, то этот индекс будем опускать. Определим вначале три оператора, позволяющих по одним функциям получать другие.

Суперпозиция. Пусть Fᵐ и fᵑ1,…fᵑm арифметические функции. Скажем, что функция Gᵐ получена из Fᵐ,.., fᵑ1,…fᵑm с помощью оператора суперпозиции (обозначение: Gⁿ = [Fᵐ; fᵑ1…fᵑm]), если для всех наборов аргументов (x1….xn)

Gᵐ(x1….xn) = Fᵐ(fⁿ1(x1…xn),…fⁿm(x1…xn))

При этом для каждого набора аргументов (а1,...,аn) функция Gⁿ(a1…an) < бесконечности (т.е. определена), если определены все значения fⁿ1(a1…an) =b1….fⁿm(a1…an)=bm и Fᵐ(b1…bm) < бесконечности.

Примитивная рекурсия. Скажем, что функция Fⁿ⁺1 (x1…xn, y) получена с помощью оператора примитивной рекурсии из функций gⁿ(x1,...,xn) и hⁿ+2(x1,...,xn,у,z), если она может быть задана схемой примитивной рекурсии:

Fⁿ⁺1 (x1…xn,0) = gⁿ(x1,..,xn)

Fⁿ⁺1 (x1…xn, y+1) = hⁿ⁺2 (x1,…xn,y,Fⁿ⁺1 (x1,…,xn,y))

В этом случае будем писать Fⁿ⁺1 = R(gⁿ, hⁿ⁺2).

При этом F(a1,…an,0)<бесконечности <=> gⁿ(а1,...,an) < бесконечности и для каждого b

F(a1,…,an,b+1) < бесконечности ó F(а1,...,аn,Ь) = с <бесконечности и hⁿ⁺2(а1,...,аn,Ь,с) < бесконечности.

В случае, когда n = 0, т.е. аргументов x1,...,xn нет, схема примитивной рекурсии принимает вид

F1(0) = a

F1(y+1) = h2(y, F1(y)), где а Є N.

 

Минимизация. Скажем, что функция Fᵐ(x1….xn) получена с помощью оператора минимизации(µ-оператора) из функции gⁿ⁺1(x1,…,xn,y) если Fⁿ(x1,...,xn) определена и равна у тогда и только тогда, когда все значения gⁿ⁺1(x1,…,xn,0),…., gⁿ⁺1(x1,…,xn,y-1) определены и не равны 0, а gⁿ⁺1(x1,…,xn,y) = 0.

В этом случае будем писать

Fⁿ(x1,..,xn) = µy [gⁿ⁺1(x1,..xn,y) = 0].

 

 

Простейшие функции. Функция называется простейшей, если она является одной из следующих: функций:

а) о1(x) = 0 - тождественный нуль;

6) Ѕ1(x) = х + 1 - следующее число (плюс один);

в) функции выбора аргумента Iⁿm (x1,…,xn)=xm (1≤m≤n).

 

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

Частично рекурсивные функции. Функция f называется частично рекурсивной функцией (ч.р.ф.). если она является одной из простейших функций или может получиться из них с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и минимизации, т.е. существует последовательность функций f1,f2,…,fn = f, каждая из которых является либо простейшей, либо получена из предыдущих с помощью одного из указанных операторов.

Функция f называется общерекурсивной функцией (о. р.ф.), если она частично рекурсивна и всюду определена.

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