Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 40
Текст из файла (страница 40)
Замечание. При определении классов Л„р и К„р предполагается, что при построении каждой конкретной функции соответствующие операции применяются не более чем конечное число раз (некоторые или все операции могут вообще не применяться). Класс К,г всех ебщерекурсивнь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) де(ж — '(чек~к). 2.8. 1) Доказатгч что однократное применение операции миними- зации к всюду определенной числовой функции приводит к функции, определенной хотя бы в одной точке.
2) Привести пример одноместной примитивно рекурсивной функ- ции, из которой двукратным применением операции минимизации можно получить нигде не определенную функцию. 3) Сформулировать условие, необходимое и достаточное для того, чтобы функция д . г"(я) была нигде не определенной. 4) Сформулировать необходимое и достаточное условие того, что числовая функция д. 1(ж) является всюду определенной. 5) Доказать, что ссли функция у(т, у) нс является всюду опреде- ленной, то таким же свойством обладает каждая из функций длу(х, у) и диу(т, у).
2.5. Применить операцию минимизации к функции г' по переменной ж, (результирукгщукг функцию представить в «аналитической» форме): 1) ((т1) = 3, г = 1; 2) ((тг) = жг + 2, г = 1; 3) г(тг) = тг †' 2, г = 1; 4) 7(тг) = тг — 2, г = 1; 5) ((тг) = 2тг + 1, г = 1; 6) ((тг) = 2тг †' 1, 1 = 1; у'2. Классы емчиелилых и рекурсивных фуякций 201 2.9. 1) У всюду определенной функции ?(х, д) обе переменные существенные. Предположим, что рх~(х, д) и ду?(х, д) -- всюду определенные функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
