Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 39
Текст из файла (страница 39)
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) У всюду определенной функции ?(х, д) обе переменные существенные.
Предположим, что рх~(х, д) и ду?(х, д) -- всюду определенные функции. Может ли хотя бы одна из этих функций зависеть существенно только от одной переменной? 2) У всюду определенной функции Дх, д) ровно одна существенная переменная. Могут ли у функции д,у(х, д) быть существенными обе переменные, если предположить дополнительно, что она всюду определена? 2.10. Обосновать вычислимость следующих функций: 1) е( ) ~ ] ( . зб(2х, )),( + 1)з. 2) Дх, д, х) = ( — '+ 2~ ?~~) ((хз — ' д) + х)); 3) ?(х, д, х) = 4л " ' — (хз+ 1)з. (зб(х — ' 2У) + я); з з 4) ((х, д, х) = У 2се т"Р-Я~х хт1 2.11.
Каковы мощности классов К„р, К,р, К„„и К„? 2. Некоторые специальные свойства рекурсивных функций. 2.12. Опровергнуть следующее утверждение: если машина Тьюринга вычисляет функцию ~з(х) Е К„р~К„р, то вычислимая на этой машине функция ?з(х, д) не является примитивно рекурсивной. 2.13.
1) Машины Тьюринга Т, и Тз вычисляют примитивно рекурсивные функции ~х(х) и ?з(х) соответственно. Следует ли отсюда, что композиция ТзТя этих машин вычисляет обязательно примитивно рекурсивную функцию? А если машины Тз и Тз правильно вычисляют функции?з и ?з? 2) Машина Тьюринга Т вычисляет примитивно рекурсивную функцию )(х). Справедливо ли следующее утверждение: если итерация машины Т вычисляет некоторую всюду определенную функцию д(х), то функция д(х) обязательно примитивно рекурсивна? 2.14. Известно, что ?(х) Е Кер и что при всех х ) 0 выполняются соотношения Д(2х) = ? (х + 1) и ?" (2х + 1) = Д(х) . Вытекает ли отсюда, что? (х) примитивно рекурсивная функция? 2.15. Функции ед(х) и дз(х) являются всюду определенными вычислимыми функциями, удовлетворяющими следующому условию: какова бы ни была примитивно рекурсивная функция у(х), найдется хс такое, что з(хс) < дз(хв) + дз(хс).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
