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

Нажмите для полного просмотра!

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №2

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №3

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №4

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №5

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №6

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №7

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №8

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №9

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №10

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №11

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №12

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №13

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №14

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №15

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №16

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №17

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №18

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №19

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №20

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №21

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №22

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №23

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №24

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №25

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №26

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №27

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №28

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №29

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №30

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №31

Примитивно-рекурсивные операторы. Частично-рекурсивные функции, слайд №32

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Примитивно-рекурсивные операторы. Частично-рекурсивные функции. Доклад-сообщение содержит 32 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

Предикаты

Слайд 3

Описание слайда:

Примитивно-рекурсивные операторы Оператор называется примитивно-рекурсивным (ПР - оператором), если он сохраняет примитивную рекурсивность функции. Условный переход или разветвление Обозначим его 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)).

Слайд 4

Описание слайда:

Оператор минимизации Определение. Функция 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)):

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Ограниченный оператор минимизации Определение 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)

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

Быстро растущие функции Чтобы показать существование функций вычислимых, но не примитивно–рекурсивных, построим такую функцию, которая растет быстрее любой примитивно–рекурсивной функции. Сначала рассмотрим известные функции сложения, умножения, возведения в степень, зная, что каждая последующая из них растет быстрее предыдущей. 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))

Слайд 17

Описание слайда:

Быстро растущие функции Продолжим последовательность функций (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 и введем в рассмотрение функцию Аккермана

Слайд 18

Описание слайда:

Функция Аккермана 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;

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

Теорема 10. Диагональная функция Аккермана растет быстрее любой примитивно–рекурсивной функции. Теорема 10. Диагональная функция Аккермана растет быстрее любой примитивно–рекурсивной функции. Доказательство. Пусть f(x) — любая примитивно–рекурсивная функция, тогдапо теореме (9) она B–мажорируема, т.е. найдется такое, что для всех x >2справедливо неравенство f(x)

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

Теорема 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).

Слайд 31

Описание слайда:

Теорема 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).

Слайд 32

Описание слайда:

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