Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 39
Текст из файла (страница 39)
Говорят также, что функция1 получена из функций у и Ь с помоьцвю операции приаипьивной рекурсии по переменной хп; используют обозна |ение З" = К(у, Ь) и указывают отдельно, по какой переменной ведется рекурсия. При задании примитивно рекурсивного описания функции 1(х), зависящей от одной переменной, схема примитивной рекурсии имеет 1"(0) = а, Р(д + 1) = Ь(дь У(д)), д > О, (2) где а константа (чнсло из множества Ьь = (О, 1, 2, ...) натурального ряда с нулем). Пусть 1(хы ..., хп ы х„) (и > Ц некоторая частичная числовая функция. Определим функцию д(хы ..., хп ь, х„) следующим образом.
Пусть оп = (оь, ..., оп. ь, оп) произвольный набор целых неотрицательных чисел; рассмотрим уравнение З(оьь. ь оп — ь д) =оьь: (3) а) если уравнение (3) имеет решение до Е Х и при всех у Е ь"ьь таких. что 0 < у < уо, функция Доы ..., о„ы у) определена и ее значения отличны от пп, то полагаем д(о") = уо, б) если уравнение (3) не имеет решений в целых неотрицательных числах, то считаем, что д(П") не определено; в) если уо наименьшее целое неотрицательное решение уравнения (3) и при некотором уь Е Х и меньшем уо значение Д(оы... ..., оп ь, уь) не определено, то полагаем, что д(о") не определено. зз* 196 Гл, г'.
Элементы теории алгоритмов О функции д(х"), построенной указанным способом из функции ~(ха), говоРЯт, что она полУчена из фУнкцпи 1(хы ..., хн ы хн) с пемещьнз операции мцнпмизации по переменной хп (или, короче, с помощью минимизации пе х„). Используются следующие, обозна- чениЯ: У = Му или д(х") = Мл„у(х"), или д(х") = Р,„()(х")), или Ых") = р У(х, "., — у) = * ) Замечание.
Операции примитивной рекурсии и минимизации можно применять по любым переменным, входящим в функции 1', д и Ь, но всегда нужно указывать, по каким переменным эти операции проводятся. Претпейщимн будем называть в дальнейшем следующие функции: а) в(х) = т+ 1 (функция следования); б) о(х) = 0 (нулевая функция), в) У„",(хы ..., х„) = х„, (1 < т ( и; и = 1, 2, ...) (селекторная функции или функция выбора аргуменпт). Класс Клп всех примитивно рекурсивных функций представляет собой множество всех функций, которые могут быть получены из простейших функций с помощью операций супсрпозиции и примитивной рекурсии.
Классом Л„„ всех частично рекурсивных функций называется множество всех функций, которые могут быть получены из простейших функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. Замечание. При определении классов Л„р и К„р предполагается, что при построении каждой конкретной функции соответствующие операции применяются не более чем конечное число раз (некоторые или все операции могут вообще нс применяться). Класс К,г всех ебщерекурсивнь1х функций представляет собой множество всех всюду определенных частично рекурсивных функций.
Нетрудно показать, что Кьр с К,ю (включение строгое). Справедливо также и строгое включение К„„с Кои (т. е, существуют общерекурсивные функции, не являющиеся примитивно рекурсивными) . Через К, будем обозначать класс всех частичных числовых функций, вычисламых на машинах Тьюринга. Т е о р е м а (о представлении вычислимых функций в специальной форме, аналог теоремы С. К. Клини о нормальной форме частично рекурсивных функций).
Для всякой вычислимей функции ~(хы..., х„) существуют такие примитивно рекурсивные функции Фу(хы... ..., х„,. хилз) и Су(х~,...., хн, х,е з), чгпо Пхз хл) = Фг(х1 хм Ря1Сг(хз . хл У) = 0)). Здесь рн(С1(х~,...., хн, у) = 0) — минимальное целое неотрицательное реп|ение уравнения Су(хы ..., хлл у) = 0 (для каждого набора значений переменных хы ..., х„); если при заданном наборе (хы..., хе ) решения нет, то р„(Су(х~,....., хв, у) = 0) не определено. 3'3.
Классы ввьниелильыт ьь рекуреивнвх функций 197 Справедливо утверждение: классы К„р и К, совпадавьп. П р и м е р 1. Обосновать примитивную рекурсивность функции Дт, у) = х+ (2 — ' у), построив описывающие ее примитивно рекур- сивные схемы.
Решение. Запишем схему примитивной рекурсии для функ- ции 1(х, у), ведя рекурсию по переменной х: ДО, у) = 2 — у = д(у), Д(х+ 1ь у) = х+ 1+ (2 — ' у) = в(У(х, у)) = Уз (хь у, в(1(х, у))). Из этой схемы следует, что для описания функции Дх, у) достаточно иметь функцию д(у) = 2 — 'у и функцию 6(т., у, т) = 1зз(х, у, в(х)).
Очевидно, что функция 6(х, у, я) представима в виде суперпозиции простейших функций. Ладим примитивно рекурсивное описание Фу ц д(у). И., 2 0 д(у + 1) = 6ь(у, д(у)) = 2-'(у+ 1) = 1 — ' у. Значит, 6ь(у., я) = 1з(уь(у)ь т), где уь(у) = 1 — у. Следовательно, надо еще построить примитивно рекурсивное опи- сание функции уь(у), которая, как нетрудно заметить, есть вк у. Легко ьр(0) = 1 = в(0), р(у + Ц = 0. Итак, Дх, у) строится из простейших функций с помощью операций суперпозиции и примитивной рекурсии. Значит, она примитивно ре- курсивная функция. Пример 2.
Применить операцию минимизации к функции Зх+2, если ту': 2, ь не определено, если х = 2. Результирующую функцию представить в «аналитической» форме. Решение. Лля каждого хв е ь"ьь ищем минимальное решение УРавнениЯ Д(У) = хв. Так как множеством значений фУнкции 1(х) является множество (Зп, + 2 ! и у'. -2) = (2, 5) С (11, 14, 17, ..., Зп+ +2ь...), то уравнение 1"(у) = хв имеет решения лишь при тв = = 2, 5, 11, 14, ...: для всякого такого хс решение единственное (оно хв — 2 ь равно 3 Принимая во внимание, что функция Д(х) при х = 2 не опреде- лена,. заключаем: найденные решения, превосходящие 2, т. е. 3, 4, ..., не являются допустимыми (см.
п. в) определения операции миними- зации). Итак, функция д(х) = р 1(х) определена только при х = 2 и х = 5; д(2) = О, д(5) = 1. В каьестве «аналитической» записи функции д(х) можно взять х — 2 х — 2 формулу 3 + з8 (6 — х) (ибо функция определена только 3 при х = 2, 5, 8, 11, ..., Зп+ 2, ..., а функция яя(6 — х) только для х ( 6, причем з8 (6 — 2) = вя (6 — 5) = О). 198 Гл. К Элементв1 теории алгоритмов 2.1. Используя в качестве исходных функций только константы и простейшие функции, построить примитивно рекурсивные схемы, описывающие следуквщие функции: 1) вр х; 2) в8х; 3) х+ у; 4) пх, где п > 2 и натуральное; 5) т — '1; 6) т — 'у 7) т.у; 8) тг; 9) тг+2уг; 1 ° ) .~=(,'," ':, щ(-;(; (О, если х+у четное, 12) х ее у = ~ ' ' ' (сумма) по модулю 2).
( 1, если х + у нечетное., 2.2. Применяя операцию примитивной рекурсии к функциям д(х) и 6(х, у, г) по переменной у, построить функцию 1(х, у) = 1т(д,. 6), записав ее в «аналитической» форме: 1) д(х) = х, 6(х, у, г) = х + г; 2) д(х) = х, 6(х, у, г) = х + у; 3) д(х) = 2", 6(х., у, г) = 2е . г; 4) д(х) = 3*, 6(х, у, г) = 3" 5) д(х) = 1, 6(х, у, г) = х †' у; 6) д(х) = 2, 6(х, у, г) = г †' х; 7) д(х) = 2х, 6(х, у, г) = (О, если х ( у; 8) д(х) = в8х, 6(х, у, г) = х в8у+г. в8х.
2.3. Доказать примитивную рекурсивность следующих функций, используя простейшие функции и функции в8х, вбх, х+у, х — 'у, х у, х Ю у (сумма по модулю 2; см. задачу 2.1, 12)): Ц /х — у!; 2) шш(х, у); 3) шах(х, д); 4) хг.угеЭгз; х) )(х, если у = О, 5 у) (целая часть отделения х па у, если у > 1; 6) а*, где а > 2 и натуральное; (а, если х = е, 7) гоо(Х) = ~ ' ' а, г КВКИЕ;Лнба ЧИСЛа ИЗ Ю:, (х в ином случае, ао если х=7,, 7,=0, 1,...,щ, ) )(.) = 1 " (с вином случае, здесь ао, аы ..., а , с какие-либо числа из Х; )(О при х четном, х при х нечетном; (1, если х = 1т, 1 = О, 1, 2,.
т(х) 1 (О в ином случае, т > 2 и натуральное; 11) (Л) Ь'Я. Классы вычислил>ых и рскурсивив х 9>дикций 199 2.4. 1) Показать,что если функция д(х) примитивно рекурсивна. то всюду определенная функция 1 (х), отличая>щаяся от 9(х) только в конечном числе точек, является примитивно рекурсивной.
2) Пусть д>(т) и дг(х) — примитивно рекурсивные функдии. По- казать, что функция ) д>(х), если а ( х < Ь, (дг(х) в ином случае, где 0 ( а ( Ь (а Е Х, Ь Е М), примитивно рекурсивна. 3) Показать, что если функции д(у), >р>(х), >рг(х) и >сз(х) примитивно рекурсивны, то функция >р>(х), если д(у) < а, 1(х, у) = >рг(х), если а < д(у) < Ь, >рз(х), если д(у) > Ь, где 0 < а < Ь (а е М, Ь е Х), примитивно рекурсивна. Условия, наложенные на функцию д(у), надо понимать так: рассматриваются все такие значения у, при которых функция д(у) удовлетворяет ука- занному соотношения>.
4) Пусть д>(х), дг(х) и дз(х., у) примитивно рекурсивные функ- ции. Показать, что тогда примитивно рекурсивна и функция г" (х, у), определяемая следующей схемой: У(о,у) =д,(у), 7(х + 1, 0) = дг(х),. У(х+ 1, 9+ 1) = дз(х, у) (здесь х > 0 и у > 0). 5) Пусть функция д(х>>..., хи >, хл) (и > Ц примитивнорекур- сивная. Показать, что следующие функции примитивно рекурсивны: а) 7>(т ) = ~9(х>, ..., х >, '>); >=О б) Л(х") = ~',9(х> .
х >-> г). >=0 6) Доказать, что функция 7 (х), определяемая соотношения- ми >'(0) = 1, >" (1) = 2, Дт+ 2) = ЗДт+ 1) — ' 2Д(п>) (т > О), явля- ется примитивно рекурсивной. 7) Показать, что следующие функции >">(х) и 1"г(х) примитивно рекурсивные: ( 1, если х = а' (1 = О, 1, 2> .,. ), >(О в ином случае, а > 2 и натуральное; б) )г(х) = [1од, (х+ 1)], а > 2 и натуральное. 200 Гл. К Элемеипеы теории алеоривемоо 7) у(жг) = ~ †' , г = 1; 9) г(тг) = ~ — ' 11) У(ты тг) = тг — 'гг, 8) г" (жг) = — '., г = 1; г = 1; 10) г'(ты тг) = 1г(ты гг), г = 2, 1 2 г= 12) ((ты тг) = з8(тг — '2тг), г = 1; 13) г(ты тг) = тг — '1/тг, г = 1,2, 14) у(ты тг) = 2" (2тг + 1), г = 1, 2; тг+1, если те=0,1,2, 15) г'(тг) = не определено, если тг = 3, 1 = 1. тг — 4, если тг > 4, 2.6.
Найти примитивно рекурсивную функцию (если она сущест- вует), из которой однократным применением операции минимизации можно получить частично рекурсивную функцию 1: 1) ((тг) = 2 — хг; 2) Д(яг) = †'; 3) ~(тг) = 4) у(жг) = з (тг — 1); 5) г(ты тг) = тг — 2тг, 6) г (ты тг) = ' '; 7) У(ты тг) = 3 тг -~-2' 8) р"(яы яг) = 2.7. Доказать, что следующие функции примитивно рекурсивны: 1) де('( — )):, 2) д,('П вЂ” '1): 3) ул(т — ' Я); 4) д,(ж — 'Ц), 5) д,(~ъ'Ягг]); 6) де(ж — '(чек~я).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
