И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года), страница 41
Описание файла
DJVU-файл из архива "Учебник Лаврова 2006-го года", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 1 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 41 - страница
задачу 10), 12. Имеем У, (х, у) = К ([а, х[, у) для некоторого а. По задаче 8 2 существует и такое, что к [а, и ) = кл. Тогда к (0) = к (л) = и. е е 244 ОТВВТЪЪ РВШВНИЯ, УКАЗАНИЯ 13. Имеем (лК (х, у), если К (х, у) определено, ля(х, у) в противном случае для подходящей примитивно рекурсивной функции я (см.
задачу 9). Далее ля(х,)(х)) = к для подходящей примитивно.рекурсивной функции Р (см. задачу 10). 14. (а) Положим Тогда Р(х, у) = К(я(х), у) для некоторой примитивно рекурсивной функции л, я = к для подходящего п. Поэтому к = к, где/— функция, построенная в задаче 13, Отсюда л, (у) = к (у) = Р(р'(п), у) =( (у). Полагаем а = Дп). (б) Применить рассуждения пункта (а) к функции (О при у= х, ~не определено при у м х. (в) Применить рассуждения пункта (а) к функции (О при ух х, я (х, у) = ~ не определено при у = х.
15. По задаче 11 существует число е такое, что х (х) = « (е, х). Полагаем 2 = к . Тогда (Р (х )) (х) = К (е, х) = х (х). 16. Определим оператор Р: О, еслиа(х) = О, (Р(р)) (х) = у(у (д (х))), еслиа(х) > 0„ не определено, если а(х) не определено. Функция я (и, х) = (Р (к )) (х) частично рекурсивна ( см. задачу 39 из з 3). Ввиду задачи 15 существует требуемая функциями.
17. Пусть а Е к (А), Ь | к (А). Если к (А) — рекурсивное множество, то функция 245 ч.(У. теОРия ллГОРитмОВ [1 4[ <Ь, еслихЕк (А), <а, если хек '(А), является общерекурсивной. Ввиду задачи 10 (б) существует число и такое, что ку(п) = кп. Имеем Дп) Ек [(А) «» п Ек (А) «»Дп) = Ь «» 7(п) ~к (А). Приходим к противоречию. 18. (а) и (б) следуют из задачи 17.
(в) Множество В = (х < 0 Е д ) нерекурсивно ввиду задачи 17. Имеем х Е В «» с(х, О) ЕА . Поэтому А нерекурсивно, 3' з (г), (д) Аналогично (в). 19. Следует из задачи 38 из 8 3. 20. Следует из задачи 1б нз й 3 и задачи 4, так как пустое множество есть р, 21. Следует из задачл 17. 22. Следует из задачи 21. 23. Следует нз задачи 38 из 8 1. 24. Следует из задачи 9. 25. Рассмотрим случай, когда п = 1. Если Р = и„то в качестве а(.т,) берем какой-либо номер пустого множества. Если Р и и, то ввиду задачи 17 из й 3 существуют примитивно рекурсивные функции а ! и аг такие, что Р = ((а[((), аг(0) < ( ~ .4'). Тогда функция г а ((), если а (() = у, не определена в остальных случаях частично рекурснвна и я (у, () = к (().
Функция а искомая. а(у) 26. (а) ( Е л () п «» Э з, 3 з ([К (х, з!) - ([ + [К (х, з ) — ([ = О). Далее применяем задачу 38 из 8 3 и задачу 25. 27. (а) (яд «» Э з (К(х, () = з). Далееприменяемзадачу38 из 83 и задачу 25. ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ (6) Пусть Ь(х,у) = О, если уел х' не определено в остальных случаях. Тогда Ь (х, у) = к (у) для некоторой примитивно рекурсивной з(х) функции я (см. задачу 3 (б) ). 28.
Следует из задачи 10. 29. Следует из задач 25 и 28. 30. (а) Следует из задач 26 (в) и 28, (в) Следустиззддачи29дляМ ((у,х) ~ у;ах). Ф 34. Рекурсивная перечислимость Х следует из зддачи 38 из 6 3. Пусть А = л . Тогда а' хЕА «ь с(х,а) ЕХ. 35. Следует из задачи 33 и существования рекурсивно перечислимого, но нерекурсивиого множества (например, см. зддачу 43 из 6 3). 36. Полагаемся (х) = х. 37. Если А — креативное и рекурсивное множество, то — А = л а для некоторого а, но(А () и ) () (- А й — и ) = и, значит, это множество не содержите(а). 38.
Пусть х = х т-сводит А к В. Строим У следующим образом. Ввиду задачи 26(е) имеем я ' (л ) =л . Полагаем У (х) = х н (х,а) в =«) и (х,а). 39. Пусть А креативно, а В рекурсивно перечислимо. Применяем задачу 25 к множеству Р =,Хх В. Имеем <Л', если х Е В, а(х) <я) в противном случае. Тогда функцияу' а(х) т-сводит В к А. 40. Следует из задач 38 и 39.
41. Ввиду зздачи 38 достаточно доказать, что Х ~ Х , где К— множество из задачи 36. Пусть Ч 1У ТЕОРИЯ АЛГОРИТМОВ Ц 41 247 ~(а), еслих Ел, л х' а(х) (а в остальных случаях. Можно считать, что а(х) — общерекурсивная функция (см. задачу 25), Функцияи(х) 7п-сводит Кк К . 2' 42.
Пусть машина Тьюринга Т правильно вычисляет функцию К (х, у), а машина Т (х) перерабатывает слово ~у,0170 в о,01 01 О. Существует примитивно рекурсивная функция т(х) такая, что 2Т2(х) = т(х). Тогда Т (х) . Т, вычисляет к . Далее см. задачу 11 из з 2. х' 43, Полагаем у' (х) = оя(х), где я — функция из задачи 27 16), а о — функция из задачи 42. .
