Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 10
Текст из файла (страница 10)
Но в таких случаях не существует алгоритма, с помощью которого можно перейти от стандартного кодирования к нестандартному (см, упр. 0.4,21) '), ь) Кодирование алгоритмов нятуряльнымн числами часто называют нумерацией алгоритмов. Одни такая иуысряция уяоминастся и упр. 0.,4.!О. „Стандяртиыи" кодироилниям соотистстяуют так называемые главные или доиусти. мыс нумерации чястнчно рекурсивных функций (см.
(Мяльцсь, !9651, (роджерс, !9671).— Прим. лерев. вл, длгояитмы !чдстичные и всюди опяеделенные! 0А.б. Проблема соответствий Поста В этом разделе мы приведем один пример неразрешимой проблемы, а именно проблему соответствий Поста, Далее эта проблема будет применяться для доказательства неразрешимости других проблем. Определение. Частный случай проблемы соответствий Поста над алфавитом Х вЂ” это конечное множество пар из Хь х Х" (т, е. множество пар непустых цепочек в алфавите Х). Проблема заключается в выяснении того, существует ли конечная последовательность (принадлежащих этому множеству и не обязательно различных) пар (х„у,), (х,, у,)... (х„, у„), удовлетворяющих условию хьхя...
х„=у,у,... у„. Такую последовательность мы будем называть решающей последовательнсппью для этого частного случая проблемы соответствий (или просто решением). Пример 0.20. Рассмотрим следующий частный случай проблемы соответствий над алфавитом (а, Ь): ((аЬЬЬ, Ь), (а, ааЬ), (Ьа, Ь)) Последовательность (а, ааЬ), (а, ааЬ), (Ьа, Ь), (аЬЬЬ, Ь) — решающая, так как (а) (а) (Ьа) (аЬЬЬ) = (ааЬ) (ааЬ) (Ь) (Ь) Частный случай ((аЬ, аЬа), (аЬа, Ьаа), (Ьаа, аа)) проблемы соответствий не имеет решающих последовательностей, так как любая такая последовательность должна начинаться парой (аЬ, аЬа), а тогда общее число букв а в первых компонентах пар, входящих в последовательность, будет меньше числа букв а во вторых компонентах. Е) Существует частичный алгоритм, который в некотором смысле „решает" проблему соответствий, А именно, можно линейно упорядочить всевозможные последовательности пар цепочек, которые можно построить по данному частному случаю проблемы.
Затем можно начать проверять для каждой последовательности, является пн она решающей. Обнаружив первую решающую последовательность, алгоритм остановится и ответит,да". Если решаю%ей последовательности не окажется, то этот частичный алгоРитм будет работать бесконечно. Однако всюду определенного алгоритма, решающего проблему соответствий ') (т.
е. выдающего правильный ответ „да" или „нет" длн любого частного случая проблемы), ие существует — можно ь ь) Пяд алфавитом Х, содержащим ие менее двух сныиолоя.— Прим. иерее. 47 гл. в НРедВАРительныР млтемлтические сВедения УПРАЖ НЕ НИЯ показать, что если бы такой алгоритм был, то с его помощью можно было бы разрешить и проблему остановки для машин Тьюринга (упр. 0,4.22), а эта проблема неразрешима (упр. 0.4.14). уйРджнеиия 0.4.1. С ...Совершенное число — это натуральное число, равное сумме всех своих делителей (включая 1, но исключая само число).
Например, 6 =1+2+3 и 28=1-~-2+4+7+ !4 — первые два совершенных числа (следующие три: 496, 8128 и 33550336).. Постройте частичный алгоритм, который для входа ! выдает иа выходе 1-е совершенное число. (До сих пор неизвестно, конечно или бесконечно множество совершенных чисел.) 0.4.2. Докажите корректность алгоритма Евклида (пример 0.16). 0.4.3. Опи шите алгоритм сложения двух и-зпачиых де ных чисел. С Сколько времени и места требует этот алгоритм десятич(т. е. каковы соответствующие функции о и)? (С . [В 1965,", ",, где обсуждается временная сложность сложения.) 0.4.4.
О ... Опишите алгоритм умножения двух и-зиачиых чисел. !967 и к Сколько времени и места требует этот алгори ? (С . [В «и [Кук и Аандераа, 1969«, где обсуждается временная сложность умножения,) 0.4.5. Дайте . . Д " алгоритм умножения двух целочисленных (п ха)- матриц. Предположим, что каждую целочисленную арифметическую операцию можно выполнить за один шаг..Какова тогда скорость (число шагов) Вашего алгоритма? Если оиа циональиа и, посмотрите работу Штрассеиа [!969«, где дается в асимптотически более быстрый алгоритм. 0.4,6. П сть Е с= у (а, Ь) . Характеристической функцией множества Е называется такое отображение гы (а, Ь)' — (О, 1), что что Е ек сиви ут(ш) — 1, если в ЕЕ, и ~л (в) =-0 в противном случае, Г1 р урсивио тогда и только тогда, когда 7' — общерек рс ная функция. 0.4.7.
П окажите, что Š— рекурсивное множество тогда и лимы. только тогда, когда оба множества Е и Е рекурсивно переч с„чис- 0.4.8. П сть Р— усть Р— частичный алгоритм, определяющий рекурпомощью Р посивио перечислимое множество Ес= ,'а, Ь)'. С ства Е и стройте алгоритм Р', который порождает все элемент и только их, т. е. его выходом должна быть бесконечная Пост ойте р й е алгоритм Р' так, чтобы для каждой пары (1 1) из 1 Аа „которого разу но м го упорядочения всех пар натуральных чисел он применял ч астнчный алгоритм Р к 1-й цепочке из множества «а Ь)* в течение ! шагов. У Определение.
Машина Тьюринга состоит из конечного множества состояний ((г), конечного множества символов ленты (Г) и функции 8 (функции переходов, или программы), которая отобра- : жает некоторое под н множество произведения Я х Г в множество ' 1~х х,, Г,'Е, )?). В множестве Г выделяется подмножество Х ым. вхооных еимволвв и о И и один символ из à — Х называется пуст ина Ть инга - Одно состояние у, называется начальным. Машина ьюриига работает иа ленте, разделенной иа ячейки, одну из которых б евает головка.
В любой момент времени Все ячейки, кроме конечного числа, заняты пустыми символа. и ур ц мащины Тьюринга называется пара (у, а',(!), где д — состояние„ а«) — непустая часть ленты, а 1 — специальный символ, показывающий, что головка обозревает ячейку, расположенную непосредственно справа от него (символ ' не является символом ленты и не занимает ячейки). Следуюи!ая конфигурация (после (д, а(«))) определяется с помощью символа о а А, обозреваемого головкой (это самый левы символ цепочки «! или пустой символ, если «) =-е), и значении состояние, А' — символ ленты и 0 Е (Е, !с). Тогда следующей конфигурацией будет (Р,а'!(У'), где а'«)' образуется из ай замей ола А стоящего справа от 1, на А' и сдвигом сим, если 1? — -Е, вола ! на одну позицию в направлении О (влево, если и вправо, если 0 ==1?).
Для того чтобы передвинуть символ 1, стоящий на конце, может оказаться необходимым добавить на этом конце пустой символ. Машину Тьюринга можно представлять себе как формальную систему, определяющую частичный алгоритм. Входом этого алгоработает, начиная с конфигурации (у„! ш) и последовательно , вычисляя следующие конфигурации.
Если машина Тьюринга оптшнавливается, т. е. достигает конфигурации, для которой следующий шаг невозможен (напомним, что у ц лена не обязательно для всех пар из !г х Г), то выходом является непустая часть ее ленты. «0.4.9. Постройте машину Тьюринга, которая для данного входа шЕ «О, 1)" напишет на ленте слово ДА, если ш — палиндром (т. е, ш=шв), и НЕТ в противном случае, причем в любом случае остановится "0.4.10. П едположим, что каждая машина Тьюринга использует в качестве состояний и символов ленты конечное д р 4в ГЛ. О.
ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ жество некоторого счетного множества символов (аю а„ая,...). Покажите, что существует взаимно однозначное соответствие между натуральными числами и машинами Тьюринга, ««0.4.11. Покажите, что не существует машины Тьюринга, которая останавливается на всех входах (т. е. задает алгоритм) и определяет по данному числу г, записанному на ее ленте в двоичной форме, останавливается ли когда-нибудь г'-я машина Тьюринга (см, упр.
0.4.10). «0.4.12. Пусть (а„аю ... ) — счетное множество сямволов. Покажите, что множество всех цепочек конечной длины, составленных из символов этого множества, счетно. *0.4.13. Опишите неформально машину Тьюринга, входами которой являются пары натуральных чисел и которая для данного входя (!, 1) останавливается тогда и только тогда, когда гья машина Тьюринга останавливается па /-й входной цепочке (см.
упр. 0.4.!2). Если при этом оиа дает тот же выход, что и гхя машина на гьй цепочке, будем называть ее' униеерсальиоп. Универсальные машины Тьюринга используются во многих доказательствах. *«0.4.14. Покажите, что не существует машины Тьюринга, останавливающейся на любом входе, который является парой натуральных чисел, и для данного входа (!, 1) печатающей на ленте ДА, если г-я машина Тьюринга останавливается на входе 1, и НЕТ в противном случае. Указание: Предположите, что такая машина существует, и получите противоречие, как в примере 0,19. **0.4.15. Покажите, что не существует машины Тьюринга, входами которой являются машины Тьюринга (т.
е. их описания) и которая для машин, задающих алгоритмы, выдает ответ ДА и останавливается, а для остальных машин ие останавливается. «0.4.10. Покажите, что проблема „остановится лн машина Тьюринга, начав работу на пустой ленте?" неразрешима, 0.4.17. Покажите, что проблема определения того, является ли высказывание теоремой в исчисления высказываний, разрешима.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
