Определение рекурсивных функций

Мы будем рассматривать частичные арифметические функции fn(x1, …, xn): Nn

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

Определение 8.1. Суперпозиция. Пусть Fm и f1n,…, fmn

- арифметические функции. Скажем, что функция Gn получена из Fm , f1n, …, fmn с помощью оператора суперпозиции (обозначение: Gn=[Fm;f1n, …, fmn]), если для всех наборов аргументов (x1,…,xn)

При этом для каждого набора аргументов (a1, …, an) функция Gn(a1, …, an)< ? (т.е. определена), если определены все значения f1n (a1, …, an)=b1,…, fmn (a1, …, an)=bm

и Fm(b1,…, bm) < ?.

Определение 8.2. Примитивная рекурсия. Скажем, что функция Fn+1(x1,… ,xn,y) получена с помощью оператора рекурсии из функций gn(x1,…, xn) и hn+2(x1, …, xn, y, z), если она может быть задана схемой примитивной рекурсии

В этом случае будем писать Fn+1 = R(gn,hn+2).

При этом

и для каждого b

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

где a

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

Определение 8.3. Минимизация. Скажем, что функция Fn(x1,… ,xn) получена с помощью оператора минимизации(?-оператора) из функции gn+1(x1,…, xn,y), если Fn(x1,…,xn) определена и равна y тогда и только тогда, когда все значения gn+1(x1,…, xn,0),…,gn+1(x1,…, xn,y-1) определены и не равны 0, а gn+1(x1,…, xn,y)=0. В этом случае будем писать

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

o1(x)=0 - тождественный нуль;
s1(x)= x+1 - следующее число (плюс один);
функции выбора аргумента Imn (x1, … ,xn)=xm (1
m
n).

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

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

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

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

Нетрудно проверить, что каждая примитивно рекурсивная функция всюду определена, т.е. является общерекурсивной (обратное, вообще говоря, неверно).

Содержание раздела