Леммы о рекурсивных функциях

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

Лемма 8.1. Рекурсивность табличных функций. Пусть всюду определенная функция f(x) на всех аргументах, кроме конечного числа, равна некоторой константе c (такую функцию назовем табличной). Тогда она является примитивно рекурсивной.

Доказательство Пусть для функции f из условия леммы nf= max{x | f(x)

c}. Доказательство проведем индукцией по nf.

При nf=0 функция f является постоянной и поэтому примитивно рекурсивной (пример 8.1).

Предположим что все табличные функции g со значением ng

k примитивно рекурсивны и пусть nf = k +1 и f(0)=a. Определим табличную функцию f'(x) = f(x+1). Ясно, что nf' = k, и по предположению индукции f' примитивно рекурсивна. Легко проверить, что тогда f задается следующей схемой:

и, следовательно, также примитивно рекурсивна.

Покажем замкнутость класса ч.р.ф. (п.р.ф.) относительно операций суммирования и произведения.

Лемма 8.2. Суммирование и произведение. Пусть функция f(x1,…, xn, y) является частично (примитивно) рекурсивной. Тогда и функции Fn+1 и Gn+1, заданные следующими равенствами

является частично (примитивно) рекурсивными.

Доказательство Действительно, эти функции задаются следующими примитивно рекурсивными схемами:

Приведем примеры использования леммы 8.2.

Пример 8.10. max_deg_div(x,y) = максимальная степень x, на которую нацело делится y.

Пусть exp(x,y) - экспоненциальная функция: exp(x,y) = xy. Ее примитивную рекурсивность легко установить, используя функцию умножения (см. задачу 8.1 (а) ). Тогда нетрудно проверить, что искомая функция задается соотношением

и, следовательно, является примитивно рекурсивной.

Пример 8.11. Ограниченная минимизация. Пусть примитивно рекурсивная функция g(x,y) такова, что для каждого x найдется y

x, для которого g(x,y) =0. Положим F(x) = mu y [g(x,y) = 0].

Тогда, по определению, F(x) является частично рекурсивной функцией.
Покажем, что, на самом деле, она примитивно рекурсивна. Действительно, определим

. По лемме 8.2 эта функция примитивно рекурсивна. Пусть для данного x y0 = ? y [g(x,y) = 0]. Тогда при i < y0 имеем h(x,i) = 1, а при i

y0 h(x,i) =0. Поэтому искомая функция F задается равенством

и также является примитивно рекурсивной.

Лемма 8.3. Кусочное задание или разбор случаев. Пусть h1(x1,…,xn), …, hk(x1,…,xn)- произвольные ч.р.ф., а всюду определенные ч.р.ф. f1(x1,…,xn), …, fk(x1,…,xn) таковы, что на любом наборе аргументов (a1, …, an) одна и только одна из этих функций равна 0. Тогда функция g(x1,…, xn), определенная соотношениями:

является частично рекурсивной.

Доказательство Действительно, gn можно представить как сумму k произведений:

Следующий класс функций, который нас будет интересовать, - это функции для однозначной нумерации пар и n-ок целых чисел и обратные им. Определим для любой пары чисел (x,y) ее номер c2(x,y)=2x(2y+1) - 1. Например, c2(0,0)=0, c2(1,0)=1, c2(0,1)=2, c2(1,1)=5, c2(2,1)= 19. Из единственности разложения чисел на простые множители следует, что функция c2: N2

N взаимно однозначно нумерует пары целых чисел. Нетрудно понять, что если c2(x,y) = z, то двоичная запись числа (z+1) имеет следующий вид: (двоичная запись y) 10x. Из такого представления можно однозначно извлечь значение x и значение y. Эти значения определяются следующими обратными функциями:

Из этих определений непосредственно следует, что для любого z выполнено равенство c2(c21(z), c22(z))=z.

Определим теперь по индукции функции cn нумерации n-ок чисел при n > 2 и обратные им координатные функции cni (1

n):

Из этих определений также непосредственно следует, что для любого z имеет место равенство cn(cn1(z), cn2 (z),…, cnn (z))=z. (Проверьте это свойство индукцией по n.)

Лемма 8.4. Рекурсивность нумерационных функций. Для любых n

2и 1

n все определенные выше функции cn и cni являются примитивно рекурсивными.

Доказательство Примитивная рекурсивность c2(x,y) устанавливается непосредственно (см.

задачу 8.1(а)). Функция c21(z) задается равенством c21(z)= max_deg_div(2,z+1) и является примитивно рекурсивной (это показано в примере 8.10). Для функции c22(z) справедливо определение c22(z) = div(2, div(2 c21(z)}, z+1) - 1) ( здесь мы используем примитивную рекурсивность функции целочисленного деления div(x,y) из задачи 8.1(e)). Примитивная рекурсивность остальных нумерационных функций следует по индукции из их определений (см. задачу 8.10).

В следующей лемме обобщается оператор примитивной рекурсии.

Лемма 8.5. (совместная рекурсия) Пpедположим, что фyнкции

in(x1,…,xn) (1 le i le k) и фyнкции ?in+k+1(x1, …, xn, y, y1, …, yk) (1

k) пpимитивно pекypсивны. Тогда фyнкции f1n+1(x1, …, xn, y), …, fkn+1(x1, …, xn, y), опpеделяемые следyющей совместной pекypсией

k) также являются пpимитивно pекypсивными.

Доказательство Обозначим чеpез

набоp пеpеменных x1,…,xn. Опpеделим следyющие пpимитивно pекypсивные фyнкции:

и положим

Фyнкция Fn+1 полyчена пpимитивной pекypсией из пpимитивно pекypсивных фyнкций и, следовательно, сама пpимитивно pекypсивна. Спpаведливость леммы тепеpь следyет из того, что для всякого

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

Мы будем рассматривать частичные арифметические функции 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

n).

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

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

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

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

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

Приведем некоторые примеры частично рекурсивных

Приведем некоторые примеры частично рекурсивных функций.
Пример 8.1. Постоянные функции.
Пусть fn(x1,…,xn)=k для всех наборов аргументов (x1,…,xn) и числа k

N. Тогда

Пример 8.2. Сложение:+2(x,y)=x+y.
Функция сложения определяется следующей примитивной рекурсией.

Следовательно, +2 =R(I11,[s1;I33]).
Пример 8.3. Умножение: ?2(x,y)=x ? y.
Используя сложение, умножение можно задать следующей примитивной рекурсией:

Следовательно, ?2 =R(o1,[+;I33,I13]).
Пример 8.4. Минус 1:

.
Нетрудно проверить, что

.
Пример 8.5. Вычитание :

, если x

y и

если x < y.
Вычитание определяется следующей примитивно рекурсивной схемой:

Следовательно,

.
Пример 8.6. Предикаты равенства и неравенства нулю:

Примитивная рекурсивность этих функций следует из равенств

Пример 8.7. Модуль разности:

.
Пример 8.8.rm(x,y)= остаток от деления y на x (при x=0 положим rm(0,y)=y).
Заметим, что

Тогда функцию rm(x,y) можно задать примитивно рекурсивной схемой

Правую часть второго равенства легко представить как функцию g(x,y,rm(x,y)), полученную с помощью суперпозиции уже построенных примитивно рекурсивных функций.
Пример 8.9. Нигде не определенная функция ?(x).
Эта функция может быть задана, например, соотношением ?(x)= mu y[ s1(y)+x=0 ].
Отметим, что все функции в примерах 8.1 - 8.8 являются примитивно рекурсивными.

Программная вычислимость рекурсивных функций

В этом параграфе рассмотрим соотношение между программно вычислимыми и частично рекурсивными функциями. Справедлива следующая

Теорема 8.1. Каждая частично рекурсивная функция программно вычислима.

Доказательство индукцией по определению ч.р.ф.

Базис: программная вычислимость простейших функций была установлена в примерах 1.1, 1.2 и 1.4.

Индукционный шаг: покажем программную вычислимость операторов суперпозиции, примитивной рекурсии и минимизации.

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

- арифметические функции, вычислимые программами ?, ?1, … , ?m так, что ??, x1(x1,…, xm) = Fm(x1,…, xm), и ??i, x1(x1,…, xn) = fin(x1,…, xn) при i=1,…,n. Пусть переменные y1, …, ym, z1,…, zn

не используются в программах ?, ?1, … , ?m. Кроме того, пусть все вспомогательные переменные этих программ - это w1, … , wr. Рассмотрим следующую программу P:

В качестве входных переменных зафиксируем x1, …, xn, а выходной - x1. Пусть в исходном состоянии x1=a1, …, xn = an. Тогда в первой строке эти значения сохраняются в переменных z1, …, zn, которые своих значений далее не меняют. Поэтому для каждого i=1,…,m-1 после выполнения фрагмента

значением переменной yi является fin(a1,…, an), x1=a1, …, xn = an, а значения всех вспомогательных переменных равны 0. Тогда после выполнения

значением каждого xi также является fin(a1,…, an), а после выполнения ? значение x1 равно ?P,x1(x1,…,xm)= Fm(f1n(a1,…, an), …, fmn(a1,…, an)). Таким образом, ?P, x1 = [F; f1, …, fn].

Примитивная рекурсия. Рассмотрим для простоты случай n=1. Пусть функция F2(x1,y) получена с помощью оператора примитивной рекурсии из функций g1(x1) и h3(x1, y, z), т.е. F2 =R(g1,h3). Предположим, что существуют программы ?1 и ?2, вычисляющие функции g1 и h3 так, что ??1,x1}(x1)=g1(x1) и ??2,x1(x1, y,z)=h3(x1,y,z). Пусть вспомогательные переменные ?2 - это z1,…, zm и они не встречаются в ?1, а переменные u1, y1 и v не используются в программах ?1 и ?2. Рассмотрим программу P: u1 :=x1; y1:=y; v:=0; ?1; пока v < y1 делай z:=x1; x1:=u1; y:=v; ?2; z1:=0; … ; zm:=0; v:= v+1 все В качестве входных переменных P возьмем x1 и y, а выходной - x1.

Рассмотрим работу P на исходном состоянии ?, в котором ?(x1)=a, ?(y)=b. При b=0 цикл не выполняется и в результирующем состоянии ?1=P(?) имеем ?1(x1)=?1(?)(x1) =g1(a)= F2(a, 0). При b > 0 цикл будет выполняться b раз, так как в его теле v всякий раз увеличивается на 1, а значение y1=b и не меняется. Перед первым выполнением ?2 все ее рабочие переменные zi равны 0, x1=a, y=0, z=F2(a, 0), а после ее выполнения x1=h3(a,0,F(a,0))=F(a,1). Предположим теперь по индукции, что перед (i+1)-ым выполнением ?2 все ее рабочие переменные zi равны 0, x1=a, y=i и z=F2(a, i). После этого выполнения x1=h3(a,i,z)=h3(a,i,F(a,i))=F(a,i+1). Тогда присваивания z1:=0; … ; zm:=0; v:= v+1 после ?2 и z:=x1; x1:=u1; y:=v; перед ее следующим выполнением установят значения переменных ?2 так, что все ее рабочие переменные zi равны 0, x1=a, y=i+1 и z=F2(a, i+1). Следовательно, после b-го выполнения тела цикла x1=h3(a,b-1,F(a,b-1))=F(a,b).

Минимизация. Предположим, что функция Fn(x1,… ,xn) получена с помощью оператора минимизации (mu-оператора) из функции gn+1(x1,…, xn,y), т.е.

Пусть программа ?1 вычисляет gn+1, так что

, и пусть рабочие переменные ?1 - это z1,…, zm. Зафиксируем переменные x1',… , xn', y';, u, z, не входяшие в

. Рассмотрим следующую программу ?:

Рассмотрим работу ? на входных значених xi = ai (i=1,…,n). В первой строке они сохраняются в переменных x'i, которые нигде в ? не изменяются, z получает значение 0, которое тоже не меняется по ходу вычисления, а u вначале получает значение 1. Поэтому условие цикла после первой строки истинно и он хотя бы один раз выполняется. Докажем, что для каждого i

1, (i+1)-ая итерация цикла выполняется тогда и только тогда, когда g(a1, …, an,0)=b1 >0, …, g(a1, …, an, i-1)=bi-1 > 0, ? останавливается после (i+1)-ой итерации цикла с результатом x1=i тогда и только тогда, когда g(a1, …, an,i)=0. При этом перед выполнением ?1

входные переменные x1,…,xn,y имеют значения a1,…,an, i, соответственно, y'= i, а все рабочие переменные zj (j=1,…, m) равны 0.

Действительно, предположив это условие, получим, что после очередного выполнения фрагмента

значение u = x1 = g(a1,…,an,i), а рабочие переменные восстанавливают нулевые значения. Если g(a1,…,an,i)=0, то u=z и в условном операторе x1 получает значение y'=i. После этого условие цикла нарушено и ? завершает работу с выходным значением x1=i =F(a1,…, an). Если же g(a1,…,an,i)> 0, то u>z и в условном операторе y' увеличивает значение до (i+1). Тогда условие цикла выполнено и перед (i+2)-ым выполнением ?1 ее входные переменные x1,…,xn,y имеют значения a1,…,an, i+1, соответственно, y'= i+1, а все рабочие переменные равны 0.

Из доказанного утверждения непосредственно следует, что

Имеет место и утверждение, обратное теореме 8.1, которое мы приводим здесь без доказательства.

Теорема 8.2. Каждая программно вычислимая функция является частично рекурсивной.

что следующие функции являются частично

Задача 8.1. Показать, что следующие функции являются частично (примитивно) рекурсивными.
exp(x,y) = xy;fact(x) = x ,!;min(x,y)= наименьшее из x и y;max(x,y)= наибольшее из x и y;div(x,y)= частное от деления y на x (пусть div(0,y)=y).
предикаты равенства и неравенства:

.
Задача 8.2. Докажите, что если f(x1,…,xn) является ч.р.ф. (п.р.ф.), то и функция g(x1,…,xn)=f(x{i1},…,xin) является ч.р.ф. (п.р.ф.) для любой перестановки (i1, …, in) чисел 1,2,…,n.
Задача 8.3. Оператор сдвига. Пусть g(x1,…, xn) - частично (примитивно) рекурсивная функция, a и b >0 - числа из N. Тогда и функция

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

- корень n-ой степени из x (целая часть).

(пусть при i

{0,1} или x= 0 log(i,x) =0).p(x)=1, если x - простое число, и p(x)=0, если x составное. pn(k) - k-ое простое число в порядке возрастания (pn(0)=0, pn(1)=2, pn(2)=3, pn(3)=5...). t(x) = число pазличных делителей числа x (t(0)=0). d(n,m,i) - i-ый знак в m-ичном разложении числа n, т.е. если

, где 0

m-1, то d(n,m,i)=ai.nod(x, y)= наибольший общий делитель чисел x и y (пусть nod(0,y)=nod(x,0) =0).
Задача 8.5.
Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) ( элементы последовательности F(x) называются числами Фибоначчи). Покажите, что функция F(x) примитивно рекурсивна.
(Указание: покажите сначала, что функция g(x)= 2F(x) 3F(x+1) примитивно рекурсивна.)
Задача 8.6.
Докажите, что если значения общерекурсивной функции f(x) изменить на конечном множестве, то получившаяся функция f'(x) также будет общерекурсивной.
Задача 8.7.
Доказать, что из функции o(x)=0 и из функций выбора Imn(x1,...,xn)=xm с помощью суперпозиции и примитивной рекурсии нельзя получить функцию s(x)=x+1 и функцию d(x) =2*x.
Задача 8.8. Пусть g(x1,...,xn,y) - примитивно рекурсивна. Доказать, что функция

примитивно рекурсивна.
Задача 8.9.
Доказать, что если функции f(x1,...,xn,y), g(x1,...,xn,y) и h(x1,..., xn,y) частично рекурсивны, то и функция