11 - Рекурсивные функции. Примитивно рекурсивные функции. Предикаты, простые числа и возвратная рекурсия. Частично рекурсивные функции (Конспект лекций), страница 2

. . , xn−1 , k + 1) + m.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓПоложивÌÃÒÓÔÍ-12ÌÃÒÓ115ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1211. Рекурсивные функции(f n (x1 , x2 , . . . , y − k), y > k;g(x1 , x2 , . . . , xn−1 , y) =0,0 6 y < k,получимns (x1 , x2 , . . . , xn ) =xnXg(x1 , x2 , . . . , i).Замечание 11.4. Функции sg(x) и sg(x) можно получить с помощью усеченной разности r(x, y) = x −· y = max {x − y, 0}. Действительно, sg(x) = 1 −· x, sg(x) = sg(sg(x)). Докажем,что усеченная разность разность есть примитивно рекурсивная функция.Имеем x −· 0 = x — примитивно рекурсивная функция. Покажем, что ϕ(x) = x −· 1 — тожепримитивно рекурсивная функция. Опять примитивная рекурсия: ϕ(0) = 0 — примитивнорекурсивна (формально), ϕ(y + ) = y = I12 (y, ϕ(y)).

Теперь, возвращаясь к r(x, y) = x −· y,можем записать r(x, y + ) = x −· y + = (x −· y) −· 1 = ϕ(r(x, y)) = I33 (x, y, ϕ(r(x, y))). Полагаяg 3 (x, y, z) = I33 (x, y, ϕ(z)), получим r(x, y + ) = g 3 (x, y, r(x, y)), что соответствует определениюпримитивной рекурсии. #11.2. Предикаты, простые числа и возвратная рекурсияR1 ∧ R 2 ,R1 → R 2 ,ÌÃÒÓR1 ∨ R2 ,R1 ∼ R 2 ,¬R1 .ÔÍ-12Теорема 11.3. Если R1 (x1 , . .

. , xn ) и R2 (x1 , . . . , xn ) — примитивно рекурсивные предикаты,то примитивно рекурсивными являются следующие предикаты:ÌÃÒÓРассмотренные функции x + y, xy и т.д. получаются с помощью алгебраических операций.Таким способом однако нельзя получить другие используемые на практике функции, например функция p(i), значением которой является (i + 1)-е по порядку простое число. Однако итакие функции являются эффективно вычислимыми и естественен вопрос, являются ли онипримитивно рекурсивными.Выделим класс целочисленных функций, принимающих лишь значения 0, 1, т.е. отображений множества Nk в множество {0, 1}.

Такие функции являются истинностными функциямипредикатов, определенных на множестве натуральных чисел. Не разделяя предикаты и ихистинностные функции, будет говорить, что n-местный предикат — это функция от n натуральных аргументов, принимающая два значения 0, 1.

В этом контексте можно говорить опримитивно рекурсивных предикатах. Выясним, как себя ведет условие примитивнойрекурсивности при выполнении обычных логических операций.ÔÍ-12ÔÍ-12ÔÍ-12в которой функция sg(x) равна 1 при x 6= 0 и 0 при x = 0, а функция sg(x) представляет еедополнение: sg(x) = 1 − sg(x).

Первую можно построить с помощью примитивной рекурсии:sg(0) = 0, sg(x+ ) = 1, где постоянную 1 можно рассматривать как функцию двух аргументов x иsg(x). Аналогично можно построить и дополняющую функцию sg(x): sg(0) = 0+ , sg(x+ ) = 0. IÌÃÒÓÌÃÒÓf n (x1 , x2 , . . . , xn ) = g1n (x1 , x2 , . . . , xn ) · sg(hn (x1 , x2 , .

. . , xn )) + g2n (x1 , x2 , . . . , xn ) · sg(hn (x1 , x2 , . . . , xn )),ÔÍ-12ÔÍ-12J Доказательство построено на представлении f n в виде композицииÌÃÒÓÌÃÒÓТеорема 11.2. Пусть g1n , g2n , hn — примитивно рекурсивные функции. Тогда примитивнорекурсивной является функция(g1n (x1 , x2 , . . . , xn ), hn (x1 , x2 , . . . , xn ) 6= 0;f n (x1 , x2 , . . . , xn ) =g2n (x1 , x2 , . . . , xn ), hn (x1 , x2 , . .

. , xn ) = 0.ÔÍ-12ÔÍ-12Согласно теореме 11.1 эта функция примитивно рекурсивна, если функция g примитивно рекурсивна. Доказать примитивную рекурсивность g — несложное упражнение.ÌÃÒÓÌÃÒÓj=0ÌÃÒÓÔÍ-12x ∨ y = sg(x + y), x ∧ y = xy, ¬x = sg(x),x → y = ¬x ∨ y = sg(x −· y), x ∼ y = sg((x −· y) + (y −· x)).f < g,f 6 g,f > g,f < g,f = g,f 6= g.J Все эти сравнения либо перестановкой двух функций, либо применением логических операцийсводятся к одному сравнению f > g. Например, f > g ≡ ¬(g > f ), (f 6= g) ≡ (f > g) ∨ (g > f ).Сравнение f > g можно выразить через ранее рассмотренные функции: (f > g) ≡ sg(f −· g).

IС предикатами могут также выполняться кванторные операции.Теорема 11.5. Если R(x1 , x2 , . . . , xn ) — примитивно рекурсивный предикат, то примитивнорекурсивны предикатыR∃ (x1 , x2 , . . . , xn ) = ∃y(y 6 xn ∧ R(x1 , x2 , . . . , xn−1 , y),R∀ (x1 , x2 , . . . , xn ) = ∀y(y 6 xn → R(x1 , x2 , . . . , xn−1 , y)и функцияµ(x1 , x2 , . . . , xn ) = min {y: ((y < xn ) ∧ R(x1 , x2 , .

. . , y)) ∨ (y = xn )} .J Утверждение о предикатах вытекает из представленийR(x1 , x2 , . . . , xn−1 , i) ,ÔÍ-12R∃ (x1 , x2 , . . . , xn ) = sgxnXi=0R∀ (x1 , x2 , . . . , xn ) =xnYR(x1 , x2 , . . . , xn−1 , i)i=0и теоремы 11.1. Примитивная рекурсивность функции µ вытекает из представления(i 6= xn ) ∧i=0iY¬R(x1 , x2 , .

. . , xn−1 , j) .j=0Здесь особенность — наличие переменного xn под знаком суммы, что не предусматривается втеореме 11.1. Обойти это можно так. ФункцияyXfn+1(x1 , x2 , . . . , xn , i) =i=0y Xi=0(i 6= xn ) ∧iY¬R(x1 , x2 , . . . , xn−1 , j)j=0Для кванторных операций будем использовать упрощенные обозначения:∀(y6xn ) R(x1 , x2 , . . . , xn−1 , y).ÔÍ-12примитивно рекурсивна. Значит, и функция µ(x1 , x2 , . . . , xn ) = µe (x1 , x2 , . . . , xn , xn ) примитивнорекурсивна.

I∃(y6xn ) R(x1 , x2 , . . . , xn−1 , y),ÌÃÒÓµ(x1 , x2 , . . . , xn ) =xn XÔÍ-12ÌÃÒÓÔÍ-12Теорема 11.4. Если функции f (x1 , x2 , . . . , xn ) и g(x1 , x2 , . . . , xn ) примитивно рекурсивны,то примитивно рекурсивными являются предикатыÌÃÒÓÌÃÒÓПредикаты можно получать как результат сравнения целочисленных функций. Если сравниваемые функции примитивно рекурсивны, то получаемый предикат тоже примитивно рекурсивен.ÌÃÒÓÔÍ-12IÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ИУ-9, МЛТА, 2009-10уч.г.J Достаточно выразить эти операции через уже рассмотренные:µe (x1 , x2 , .

. . , xn , y) =ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ116ÌÃÒÓÔÍ-12ÌÃÒÓ117Как и кванторные операции, операция минимизации допускает вариации с заменой неравенствана нестрогое или на двойное неравенство.Предикаты позволяют ввести новые примитивно рекурсивные функции, например:1) x ... y — предикат x делится на y“;”2) Pr(x) — предикат число x простое“;”3) π(i) — функция, значением которой является (i + 1)-е (в порядке возрастания) простоечисло.Предикаты x ... y и Pr(x) можно записать с помощью логических и кванторных операций:(x ... y) ≡ ∃(i6x) (x = iy),Pr(x) ≡ ¬∃(i<x)((i > 1) ∧ (x ... i)).ÔÍ-12ÔÍ-12µ(y6xn )R(x1 , x2 , . . .

, xn−1 , y) = min {y: (y < xn ∧ R(x1 , x2 , . . . , y)) ∨ y = xn } .и другие, отличающиеся типом неравенства (здесь ∇ — один из двух кванторов). Аналогичноеобозначение введем для операции минимизации µ:ÌÃÒÓС помощью этих базовых кванторных операций можно получить другие операции, также приводящие к примитивно рекурсивным предикатам, если исходные предикаты примитивно рекурсивны:∇(y<xn ) R(x1 , x2 , . .

. , xn−1 , y), ∇(k6y6xn ) R(x1 , x2 , . . . , xn−1 , y)ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-1211. Рекурсивные функцииÔÍ-12в котором только конечное число показателей ci отлично от нуля (ненулевые показатели соответствуют реальным простым множителям в разложении числа x). В результате каждомуненулевому числу поставлена в соответствие последовательность натуральных чисел, в которойтолько конечное число элементов ненулевое (финитная последовательность).

Здесь возникаютфункции: c0 как функция x, c1 как функция x и т.д.Введем обозначение pwi (x) для коэффициента ci в разложении (11.1) числа x. Полагаемpwi (0) = 0. Получаем для каждого i функцию pwi , которая оказывается примитивно рекурсивной. Действительно,pwi (x) = µ(y<x) (x ... π(i)y ) ∧ ¬(x ... π(i)y+1 ) .ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Здесь использован элементарный факт, что число π(x+ ), т.е. первое простое число, следующееза π(x), не превышает π(x)! + 1.

Действительно, число π(x)! + 1 не делится ни на одно изпростых чисел π(1), . . . , π(x). Значит, либо оно простое, либо у него есть простой делитель,отличающийся от указанных. Поэтому в интервале [π(x) + 1, π(x)! + 1] есть простые числа.Взяв среди таких простых чисел наименьшее, получим π(x+ ).В операторе µ, использованном при определении π(x), задано сложное условие. Такое условие можно реализовать следующим образом. С помощью предиката Pr(x) строим функциюдвух переменных g(x, y) = µ(i 6 y)(Pr(i) ∧ (i > x)), которая возвращает первое простое числона промежутке x < i < y или число y, если на указанном промежутке нет простого числа. Тогдапримитивную рекурсию для функции π(x) можно определить так: π(x+ ) = g(π(x), π(x)! + 1).Остается убедиться в том, что x! — примитивно рекурсивная функция.Каждое натуральное (ненулевое) число x можно разложить на простые множители, т.е.представить в виде x = pa11 pa22 .

. . pakk . Такое разложение единственно, если простые множители pi пронумерованы по возрастанию. Более того, такое разложение можно записать в видебесконечного произведенияx = π(0)c0 π(1)c1 . . . π(n)cn . . .(11.1)ÌÃÒÓÌÃÒÓπ(x+ ) = µ(π(x) < i 6 π(x)! + 1) Pr(i).ÔÍ-12ÔÍ-12π(0) = 2,ÌÃÒÓÌÃÒÓФункцию, перечисляющую простые числа, можно задать с помощью примитивной рекурсииследующим образом:ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ИУ-9, МЛТА, 2009-10уч.г.hn+1 (x, 0) = f n (x),hn+1 (x, y + 1) = g n+s+1 (x, y, hn+1 (x, t11 (y)), .