Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 72
Текст из файла (страница 72)
3). 2) Можно удалить два первые функции, так как г -4я(х., х) = уиг(х), згг(гт(ги 4(х))) = ун а(х), я(х, 4=а(х)) = г — (х), г я(х, у) = г„л„Ц а(х, у), гз-, (х, у)) и у„из(х, у) = 1 —, Ц,,„(х, уу(у))). 3) Можно удалить две первые функции, так как: а) уг(~, я(х, х) = угз(х); б) из уй с помощью опералнй объединения, отождествления входов и обратной связи строится 1' — а(х); в) ) нуЦиа(х), у) = агу(у): г) гг з,я(х, у) = ггт(гг,,нуЦ вЂ” (х), уи; д) ~„ъя(х, У) = 1 — (1„, а,г 41 ау(х, У), 1таз(х, У)).
356 Ответы, указания, решеннв 4) Можно удалить )к(х), ибо 1 чЯеег;(уна1х)) гу (У)) = уу(У). 5) Можно удалить первую и третью функцию, так как: а) с помощью операций объединения, отождествления входов и обратной связи из последней функции системы А получается функция упг(х); б) из 1",.у У(х, У) и 1" — е (х) можно пОстРоить всЯкУю поРожденнУю фУнкцию из Рг.
в; в) уг1х) = )т11к(уг 11 — (У вЂ” (х))))). 2.20. 1) Содержится, ибо Згг(х) = ЗггЦ~к(ут(х))) и увв(х) есть в Еэг,(х))ео, о, о,1. 2) Содержится. 3) Содержится, ибо у,,в(х, унв(х)) = ут (х), а уле(х) есть в ~Фг(х))<оь о„оП 4) Содержится. Указание. Вводя обратную связь во второй и третьей функциях, получаем уг(х) = )01) и бг(х) = )10) . Затем надо воспользоваться г'гчг(х У).
5) а) Не содержится. Указание. Установить, что каждая функция из А «сохраняет» множество последовательностей е' = 1о" = огог... ое... ~ Ззе (ге ((1 > ев) ~ ~ (о = О)))Ч ЗП ГУ1 ((1 > 1 ) ~ <о = 1)))). б) Содержится. У к а з а н и е. Рассмотреть функцию, получающуюся из функции угг(уг,(ут (х))) введением обратной связи. 2.21. 1) Добавить 1',„Е „0(х, у, г).
2) Добавить з"„(х, у). 3) Добавляя только одну функцию из В, систему до полной расширить нельзя. Указание. Замкнутые классы, получающиеся при этом, состоят из функций, сохраняющих множество последовательностей 1е, описанное в ответе к задаче 2.20, 5), а). Значит, в них не содержится, например, функция 1(х) = )01)"'. При обосновании свойства сохранения множества Ъ' в случае рассмотрения операции обратной связи удобно использовать представление о.-д. функции ек которой применяется операция обратной связи) в виде канонических уравнений.
4) Добавить |, к1х, Згг(гу)). 5) Добавить 1" —,(1гг(гу)). Глава У 1.1. 1) а) Т(Р) = 1 . 6) Т(Р) = 1. в) К слову 1в не применима. 2) а) Т(Р) = 1з01. 6), в) Т(Р) = 1г. 3) а) ТЕР) = 10 1г01'. 6) Т(Р) = 10 1з. в) Т(Р) = 101гОг1. 4) а)-в) К данному слову не применима. 5) а) К слову 1г не применима. 6) Т(Р) = 1з. в) Т(Р) = 1 . 1 2. 1) Одна из возможных машин залается такой программой: уз1дг 1Л.
2) Программа одной из таких машин: дгОдгОВ, дг1уг1В. 3) Программа одной из таких машин: угОдгОЯ, дг1дг1Я. 1'ж )г. Эпемепшы гпеорип ипгоришиов 357 4) Одна из возможных машин задается следующей программой: узОдгОЛ, Ф1дг1й, узОугОЛ. 1.3. Ц а) доЦ01]г, 2) 6) 1]10]~уо1. 3) 6) 10до1 01. 4) а) 1'Овдо1. 5) а) 1гОг1до01.
в) ]10]гОда1г. 1.4. 3) Программа одной такой машины имеет вид угОуг07' уйу«ОЛ дв1ув1Л двОдзОЛ дгОдзОЛ, двОузОВ даОдг15 дв1дв17 уг1уг15 дзгдз1Л дгОдв07 дзОдоОЛ дзОувуй дг1уг17 1.5. 2) Пусть дог, ..., уо„, (~п, > Ц все заключительные состояния заданной машины Тьюринга. Нужную машину можно построить так: заменяем каждую команду вида д,одаг~Ю (о, Б символы внешнего алфавита, 77 Е 1Б, То Л)) на командУ д,одг)г77, где д,' новое состоание (длк каждого состояния уо, свое). 1.6. Для построония машины Т достаточно добавить ш дополнительных (новых) состояний у], ..., д,„и «пополнить» программу машины Т, например, такими командами; дгодзоБ, ..., д,„од,„оБ, где о . - какой-то фиксированный символ из внешнего алфавита.
1.7. Таких машин 15. 1.8. Ц Одна из возможных программ: дг1дг07о дгОдо1Б, дг1уг15. 2) Одна из подходящих программ: дгОдгОЛ, уг1уо1Л. 5) Одна из возможных программ: дгОдг1Л, дг01з1Л,, д~Одыг1Л.. ; ди — гбдгг1Л, дг~0до1Б, Ф1дг1Л, дг1дз1Л. °, д 1д +г1Л, ° °, дг~ — г1дг~1Л. 1.9. Ц а) Композиция ТгТ к 1 0 1 не применима. 2) а) (ТгТг)(Р) = 1]10]']01]з1. 3) 6) (Т,Тг)1Р) = 1'01г02'1'-, 1.10. Ц а), б) Указанная итерация к словам вида 1зк и 1зз ы (й > Ц, не применима. в) Итерация применима к любому слову вица 1~к+а (й > Ц, и в результате получается слово 1.
3) Итерация к данным словам применима, результат слово 1г'~в~'. 1.11. Ц Т(Р) = 10 1. 2) 6) Т(Р) = 1'0101в01'01. 1.12. 2) пТг ]дга ] Тг ]у]о аз ]ТгТвТв ] г,з г г з 3) оТз Що ] Те ]два Тг(Р) = ТгТгТзТзТ4] ]Та ]ТгТзаг. з г г г з 1.13. Ц Т(Р) = 1*01'~". 2) Т(Р)=1', если х>у>1, Т(Р)=1о, если р>х=1, и Т(Р)= =1" 01" '"',если у>х>2. 1.14. 6) Функция определена только при х = О., 1.
Одна из возможных программ такова: дгОуо1Б, д~1дг1Л, дгОдг1Л, дг1дз1Л, дз1дз1Б. 12) Указание. Функция определена только на следующих парах значений аргументов: (О, Ц, (О, 2), (1, Ц и (2, )7), где Л > 1. 1.15. 3) Функдия определена только нри х = 2, 3. Одна из возможных программ: дгОда1Б, дг1дгОЛ, угОугОБ, дг1дзОЛ, дзОдзОБ, дз1дзОЛ, двОдг1Ь, д41двОЛ, дзОд41й, уз1дз1Б. 1.16. Ц Дх)=хе-1, ~(х,р) =х-~у-е1. 3) Дх) =О, ~(х, у) =уф1. 6) 1(х) нигде не определена, 1(х, у) = р. 358 Ответы, указания, решенвв 1.17. Если машины начинают работу с самой левой единицы кода числа х, то вычисляются следующие три функции; х, х — 1 и нигде не определенная. 1.18. Ц Подходящая программа: дгОдз177, дг1дгИй дгОдгОЙ, д 1дг171, дз0940В, дз1д41В, д40до18.
1.19. Ц а) Ленному 1-кратному коду соответствует решетчатый код, расположенный на двух решетках, со следующей парой слов: 1 и 11. Значит., надо построить машин) Т, удовлетворяющую условию: начав работу на первой единице слова 1 0'1гг, она выдает слово 1101 (решетчатый код набора (О, Ц), Подходящая программа: дгОдгОЯ, дг1дгОй„дгОдгОН., дг1дзОЙ, дз0941п, дз1дзОге, д40де1ге, двОдвОп, д«0до1Б. 2.1. 4) 7(х) = их 7(0) = и 0 = О, 7(х -Ь Ц = Цх, 7(х)) = гг(х+ Ц = = их -Ь и. = 1(х) -> и = в(з ... в(1'(х))...).
Значит, оэ Мх, у) = (в " (у) " ) = 1гг(х: ( в(у) " )) 7) Указание. Пля требуемого примитивно рекурсивного описания функции х ° у на «первом этапе» нужны функции у(х) = 0(х) и 1г(х, у, г) = х+1,,(х, у, г). «Второй этап» связан с описанием функции 1г(х, у, з). 2.2. Ц 7(х, у) = х(у+ Ц. 2) 1(х, у) = х+ (у — ' Ц. 4) 7" (х, у) = 3'то1о 'У . 5) 7'(х, у) = зКУ -Ь (х — (у — ' Ц) зК у. 7) Д(х, у) = (2х) зКУ+ (у — ' Ц еК ((у — ' Ц вЂ” 'х). 8) Х(х, у) =зК х зКу-Ьх БК(у — 'Ц. 2.3.
3) шах(х, у) = (х — ' у) + у. 8) Указание. 1(х) = ~ а, . зК [х — г[ 4- с . П зК [х — г[. =о =о 9) Указание. Д(х) = х Х(х), где 1Е(х) = х — '2[х/2) .-. характеристическая функция множества нечетных чисел. 10) 1" (х) = зК(х — 'т [х/т)). 1Ц Указание. [зггх-Ь1 = [тех) 4-дг(х), где дг(х) =зК(([ьгх)-~Ц вЂ” '(х + Ц). 2.4.
7) а) Указание. 1г(х) получается из примитивно рекурсивной ,((х у) = ~~' зК [х — а'[ отождествлением переменных х и у. =.о б) Указание. уг(х-1- Ц = уг(х)-> уз(в+2), где уз функция из задачи а). 2.5. Ц зК [хг — 3[ — 1. 2) хг — 2. 3) х~ + 2. 5) (хг — Ц,12. 6) ((хг -1- Ц.зКхг)/2. 9) (6хг — 4) зКхг. 10) (хг — хг) -~-(хг — хг). 12) (вКхг) . (2хг -~- Ц7зК(2 — 'хг). 359 Га. г7, Графы и сесин 14) 1о8 (х1/(2хг + Ц) пРи г = 1; (хг — 2 ')/2" т~ пРи г = 2. 15) (хг — Ц/зб(3 — ' х1). 2.6. Ц 2 — 'хг.
2) 2хг. 3), 4) Такой функции нет. 5) хг г-2хг. 6) Зхг -~-хг. 7) хг . (хг -~-2). 8) хг (1 — 'хг). 2.7. Ц р,,юх — ' Ц/2]) = (2х 4- Ц збх. 4) р, (х л— [х/3]) = (З[х/2]+ Ц вЂ” '2 з8 (х х— 2[х/2]). 5) Р ([ъ'хг]) = [багха] + зб(х — '[згх]~). 6) р*(х х— [тих])' = х+ [(х+ Ц!2]г. 2.8.
2) ф( ) = 1. 3) Функция 1(х) должна быть не определена при х = О. 4) ф(х) всюду определена и принимает каждое значение из множества (О, 1, 2,... ]. 2.9. Ц Не может. 2) Не могут. 2.13. Ц Не следует. Если же машины Тг и Тг правильно вычисляют примитивно рекурсивные функции уг и фг (соответственно), то их композиция ТгТг вычисляет (причем «правильным образом>) функцию гг(г г (х)).
2) Не спранедливо. 2.14. Да, вытекает. 2.16. 2)-8) Указание. Лостаточно построить соответствуюшую суперпозицию над множеством, содержшцим заданную функцию и подходящие функции из совохупности (О, 1, 2х, хг). Например, для функции из задачи 5) имеем ф(х 1 ) = ф(х). Затем надо провести рассуждение от противного. 2.17.
Указание. Построить машину Тьюринга, вычисляюшую следуюшее обшерекурсивное доопределение функции 1(х): / ф(х), осли в точке х функция ф(х) определена, ф(х) = ( х, если в точке т функция 1(х) не определена. 2.18. Ц Полной системой не является. 2), 3) Полная система. Глава Ы 1.2. Ц Указание. Такой граф один.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
