🗊Презентация Примитивно-рекурсивные операторы. Частично-рекурсивные функции

Примитивно-рекурсивные операторы Частично-рекурсивные функции

Предикаты

Примитивно-рекурсивные операторы Оператор называется примитивно-рекурсивным (ПР - оператором), если он сохраняет примитивную рекурсивность функции. Условный переход или разветвление Обозначим его B, который по функциям q1(x1,…,xn), q2(x1,…,xn) и предикату P(x1,…,xn) строит функцию f(x1,…,xn)=B(q1, q2, P): f(x1,…,xn)= q1(x1,…,xn), если P(x1,…,xn) истинно. q2(x1,…,xn), если P(x1,…,xn) ложно. f(x1,…,xn)=q1(x1,…,xn) p(x1,…,xn)+q2(x1,…,xn) (1- p(x1,…,xn)).

Оператор минимизации Определение. Функция f(x1, …, xn) получается оператором минимизации из предиката P (x1, … , xn, z), если в любой точке (x1, x2, …, xn) значением функции f(x1, …, xn) является минимальное значение z, обращающее предикат P (x1, …, xn, z) в истину. Оператор минимизации имеет обозначение f(x1, …, xn) = µz(P (x1, …, xn, z)):

Пример f(x)=µy(2·y=x+4).  

Ограниченный оператор минимизации Определение 3.4. Функция f (x1, … , xn) получается ограниченным оператором минимизации из предиката P(x1, … , xn, z) и граничной функции U (x1, … , xn), если в любой точке значение этой функции определяется следующим образом: а) существует z < U (x1, … , xn) такое, что P (x1, … , xn, z) = “истина “, тогда f (x1, … , xn) = µz(P(x1, … , xn, z) ) , б) не существует z < U (x1, … , xn) такое, что P (x1, … , xn, z) = “истина”, тогда в качестве значения функции принимается значение граничной функции: f (x1, … , xn) = U (x1, … , xn)

Ограниченный оператор минимизации (-оператор)

Теорема 2. Функция является примитивно–рекурсивной при условии примитивной рекурсивности функции Доказательство. Представим с помощью схемы примитивной рекурсии от примитивно–рекурсивных функций: Теорема 2. Функция является примитивно–рекурсивной при условии примитивной рекурсивности функции Доказательство. Представим с помощью схемы примитивной рекурсии от примитивно–рекурсивных функций:

Теорема 3. Функция является примитивно–рекурсивной, если функция примитивно рекурсивна. Теорема 3. Функция является примитивно–рекурсивной, если функция примитивно рекурсивна. Доказательство. Запишем в виде суперпозиции ПРФ: Здесь – характеристическая функция предиката которая является ПРФ, т.к.

Теорема 4. Функция является примитивно–рекурсивной, если функции, примитивно рекурсивны. Теорема 4. Функция является примитивно–рекурсивной, если функции, примитивно рекурсивны. Доказательство. Доказательство очевидно, т.к. функция является суперпозицией заданных примитивно–рекурсивных функций и функции, примитивно–рекурсивной по теореме 3.

Теорема5. Функция является примитивно–рекурсивной, если функция примитивно рекурсивна. Теорема5. Функция является примитивно–рекурсивной, если функция примитивно рекурсивна. Теорема6. Функция является примитивно–рекурсивной, если функция примитивно рекурсивна. Теорема7. Функция если функции, примитивно рекурсивны.

Теорема 8. Функция построенная с помощью ограниченного оператора минимизации из примитивно–рекурсивного предиката и примитивно–рекурсивной функции , является примитивно-рекурсивной. Теорема 8. Функция построенная с помощью ограниченного оператора минимизации из примитивно–рекурсивного предиката и примитивно–рекурсивной функции , является примитивно-рекурсивной. Доказательство. Представим функцию в виде вспомогательной примитивно–рекурсивной функции и покажем, что в любой точке эти функции равны. Рассмотрим функцию В соответствии с определением функции рассмотрим два случая вычисления функции 1. Не существует такое, что . Тогда для любого имеем , следовательно для любого Следовательно в соответствии с (*) Функция по определению в этом случае также равна .

Доказательство (продолжение) Доказательство (продолжение) Рассмотрим второй вариант вычисления функции (*): пусть найдется такое , что , тогда … Следовательно … … Тогда сумма (*) равна z в соответствии с определением ограниченного µ-оператора значение также равно z. Т.о., в любом случае можно представить выражением (*): функции и эквивалентны. Но функция является суперпозицией ПРФ, следовательно она ПРФ, а значит и функция ПРФ.

Примеры Доказать, что функция является ПРФ. Показать, что τ(x) — число делителей числа x — является примитивно–рекурсивной функцией.

Достаточно ли класса примитивно–рекурсивных функций для построения определения любого алгоритма?

Быстро растущие функции Чтобы показать существование функций вычислимых, но не примитивно–рекурсивных, построим такую функцию, которая растет быстрее любой примитивно–рекурсивной функции. Сначала рассмотрим известные функции сложения, умножения, возведения в степень, зная, что каждая последующая из них растет быстрее предыдущей. P0(a, x) = a + x; P1(a, x) = a · x; (1) P2(a, x) = ax. Рассмотрим рекурсивное определение каждой из этих функций через предшествующие функции: P1(a, 0) = 0; P1(a, x + 1) = a · (x + 1) = a + P1(a, x) = P0(a, P1(a, x)); (2) P2(a, 0) = 1; P2(a, x + 1) = ax +1 = ax · a = P1(a, P2(a, x))

Быстро растущие функции Продолжим последовательность функций (1), для чего введем в рассмотрение множество функций Pn(a, x): P0(a, x) = a + x; Pn+1(a, 0) = sg(n); (3) Pn+1(a, x + 1) = Pn(a, Pn+1 (a, x)) Очевидно, что характер функций Pn(a, x) существенно зависит от n и x, значение переменной a при фиксированных n и x принципиально не меняет тип возрастания функции. Поэтому для анализа поведения функций Pn(a, x) зафиксируем a = 2 и введем в рассмотрение функцию Аккермана

Функция Аккермана B(n, x) = Pn(2, x) или в соответствии с определением (2) B(0, x) = 2 + x; B(n + 1, 0) = sg(n); B(n + 1, x + 1) = B(n, B(n + 1, x)) Диагональная функция Аккермана: A(x) = B(x, x) Можно доказать, что функция Аккермана обладает следующими свойствами: B(n, x) ≥ 2x при n ≥ 2 , x ≥ 1; B(n, x + 1) ≥ B(n, x) при n, x ≥ 1; B(n + 1, x) ≥ B(n, x + 1) при n ≥ 1, x ≥ 2; B(n + 1, x) ≥ B(n, x) при n ≥ 2, x ≥ 2;

Функция Аккермана простой пример всюду определённой вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается A(m, n). Эта функция растёт очень быстро, например, число A(4, 4) настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной.

Определение 3.5. Функция называется B–мажорируемой, если существует такое N ≥ 0, что в любой точке (), где все

Теорема 9. Любая примитивно–рекурсивная функция Теорема 9. Любая примитивно–рекурсивная функция B–мажорируема. Доказательство. В соответствии с определением примитивно–рекурсивных функций доказательство проведем в три шага. Сначала покажем, что простейшие функции B–мажорируемы: Затем покажем, что оператор суперпозиции позволяет получать B-мажорируемые функции. Для простоты рассмотрим функции одного аргумента. Пусть f(x)=g(h(x)), где g(x) и h(x) – В-мажорируемы: Тогда

Доказательство (продолжение 1) Доказательство (продолжение 1) Следовательно функция В-мажорируема. Теперь покажем, что из В-мажорируемых функций с помощью оператора примитивной рекурсии можно получить только В-мажорируемую функцию. Пусть Рассмотрим начальную точку x=3, соответствующую определению В-мажорируемой функции:

Доказательство (продолжение 2) Доказательство (продолжение 2) Рассмотрим варианты вычисления Пусть , тогда Пусть , тогда )=

Теорема 10. Диагональная функция Аккермана растет быстрее любой примитивно–рекурсивной функции. Теорема 10. Диагональная функция Аккермана растет быстрее любой примитивно–рекурсивной функции. Доказательство. Пусть f(x) — любая примитивно–рекурсивная функция, тогдапо теореме (9) она B–мажорируема, т.е. найдется такое, что для всех x >2справедливо неравенство f(x) <B(n,x). Тогда f(x + n) <B(n,x + n) ≤ B(x + n,x + n) = A(x + n) Указанное неравенство справедливо для произвольной примитивно–рекурсивной функции. В частности, если функция A(x) является примитивно–рекурсивной, то для неедолжно выполняться неравенство A(x + n) < A(x + n) Полученное противоречие означает, что функция A(x) не является примитивно–рекурсивной функцией. Следствие. Примитивно–рекурсивные функции нельзя использовать для определения понятия алгоритма. Это следует из того факта, что существует алгоритм вычисления функции A(x), но примитивно–рекурсивной эта функция не является.

Частично-рекурсивные функции Определение 6. Частично–рекурсивной называется функция, построенная из простейших с помощью конечного числа операторов суперпозиции, примитивной рекурсии и неограниченной минимизации. Определение 7. Всюду определенная частично–рекурсивная функция называется общерекурсивной или просто рекурсивной функцией.

Тезис Чёрча Всякий алгоритм может быть реализован частично–рекурсивной функцией В силу тезиса Черча вопрос о вычислимости функции или, что то же самое, о существовании алгоритма ее вычисления, равносилен вопросу о ее частичной рекурсивности. Понятие частично–рекурсивной функции — строгое математическое, поэтому обычные математические методы и приемы позволяют непосредственно доказать, что решающая задачу функция не может быть рекурсивной и тем самым доказать неразрешимость проблемы.

Рекурсивные и рекурсивно перечислимые множества Определение 3.8. Подмножество A множества всех натуральных чисел N называется рекурсивным (примитивно–рекурсивным), если характеристическая функция множества A частично–рекурсивна (соответственно, примитивно–рекурсивна). Так как все примитивно–рекурсивные функции являются частично–рекурсивными, то каждое примитивно–рекурсивное множество является рекурсивным. Обратное неверно.

Проблема вхождения Проблемой вхождения числового множества A называется задача отыскания алгоритма, который по стандартной записи числа a в некоторой системе счисления позволяет узнать, входит число a в A или нет, т.е. указанный алгоритм позволяет вычислять значение характеристической функции множества A. В силу тезиса Черча существование такого алгоритма равносильно рекурсивности характеристической функции. Поэтому можно сказать, что рекурсивные множества — это множества с алгоритмически разрешимой проблемой вхождения.

Свойства рекурсивных и примитивно–рекурсивных множеств Характеристическими функциями пустого множества Øи множества натуральных чисел N являются функции–константы 0 и 1 соответственно. Эти функции примитивно–рекурсивны. Поэтому множества Øи N также примитивно–рекурсивны. Характеристической функцией для конечного множества чисел является примитивно–рекурсивная функция Поэтому каждое конечное множество натуральных чисел примитивно–рекурсивно.

Теорема 11. Дополнение рекурсивного (примитивно–рекурсивного ) множества, а также объединение и пересечение любой конечной системы рекурсивных (примитивно–рекурсивных ) множеств есть множества рекурсивные (примитивно–рекурсивные). Теорема 11. Дополнение рекурсивного (примитивно–рекурсивного ) множества, а также объединение и пересечение любой конечной системы рекурсивных (примитивно–рекурсивных ) множеств есть множества рекурсивные (примитивно–рекурсивные). Доказательство. Пусть f1(x), f2(x), ... , fn(x) — характеристические функции множеств A1, A2,...,An. Тогда функции f(x) = sg(f1(x)); h(x) = sg(f1(x) + f2(x) + … + fn(x)) g(x) = f1(x) · f2(x) · … · fn(x); будут характеристическими множествами соответственно для дополнения множества A1, объединения и пересечения множеств A1, A2,...,An. Если f1(x), f2(x),...,fn(x) — частично–рекурсивные (соответственно, примитивно–рекурсивные) функции, то такими же будут и функции f(x), g(x), h(x). Теорема 12. Если всюду определенная функция f(x) частично–рекурсивна (примитивно–рекурсивна ), то множество A решений уравнения f(x) = 0 рекурсивно (примитивно–рекурсивно ). Доказательство. Характеристической функцией множества A служит функция sg(f(x)), рекурсивная или примитивно-рекурсивная вместе с функцией f(x).

Теорема 13. Если примитивно–рекурсивная (общерекурсивная ) функция f(x) удовлетворяет условию Теорема 13. Если примитивно–рекурсивная (общерекурсивная ) функция f(x) удовлетворяет условию то совокупность значений M этой функции есть множество примитивно–рекурсивное (рекурсивное ). В частности, условие теоремы выполняется для возрастающей функции. Доказательство. По условию теоремы , следовательно, для любого заданного x можно рассмотреть все натуральные числа i ≤ x, вычислить значение функции f(i), а затем сравнить его с x. Равенство x = f(i) выполняется тогдаи только тогда, когда x является значением функции f(i). Из этого равенства следует, что Следовательно, в процессе проверки для всех 0 ≤ i ≤ xполучим тогда и только тогда, когда x — значение f(i). Тогдахарактеристической функцией множества M служит функция рекурсивная или примитивно-рекурсивная вместе с функцией f(x).

Определение 3.9. Множество чисел A называется рекурсивно перечислимым, если существует такая рекурсивная функция f(x,y),что уравнениеf(a,y) = 0имеет решение тогда и только тогда, когда . Определение 3.9. Множество чисел A называется рекурсивно перечислимым, если существует такая рекурсивная функция f(x,y),что уравнениеf(a,y) = 0имеет решение тогда и только тогда, когда . Таким образом, множество натуральных чисел является рекурсивно перечислимым, если оно либо пустое множество, либо есть область значений некоторой рекурсивной функции. Если мы принимаем тезис Черча, то, говоря неформально, можно считать, что рекурсивно перечислимым является всякое множество натуральных чисел, порождаемое каким–либо алгоритмическим процессом. Пример. Множество квадратов натуральных чисел рекурсивноперечислимо, т.к. оно просто задано уравнением .