Главная Промышленная автоматика.

жество некоторого счетного множества символов {а, а, й, ...]. Покажите, что существует взаимно однозначное соответствие между натуральными числами и ман1инами Тьюринга.

**0.4.11. Покажите, что не существует машины Тьюринга, которая останавливается на всех входах (т. е. задает алгоритм) и определяет по данному числу /, записанному на ее лейте в двоичной форме, останавливается ли когда-нибудь /-я машина Тьюринга (см. упр. 0.4.10).

*0.4.12. Пусть {а, а, ...} - счетное множество символов. Покажите, что множество всех цепочек конечной длины, составленных из символов этого множества, счетно.

*0.4.13. Опишите неформально машину Тьюринга, входами которой являются пары натуральных чисел и которая для данного входа (/, у) останавливается тогда и только тогда, когда i-я машина Тьюринга останавливается на /-й входной цепочке (см. упр. 0.4.12). Если при этом она дает тот же выход, что и i-я машина на /-й цепочке, будем называть ее" универсальной. Универсальные машины Тьюринга используются во многих доказательствах.

**0,4.14. Покажите, что не существует машины Тьюринга, останавливающейся на любом входе, который является парой натуральных чисел, и для данного входа (i, /) печатающей на лейте ДА, если i-я машина Тьюринга останавливается на входе /, и НЕТ в противном случае. Указание: Предположите, что такая машина существует, и получите противоречие, как в примере 0.19.

**0.4.15. Покажите, что не существует машины Тьюринга, входами которой являются машины Тьюринга (т. е. их описания) и которая для машин, задающих алгоритмы, выдает ответ ДА и останавливается, а для остальных машин ие останавливается.

*0.4.16. Покажите, что проблема „остановится лн машина Тьюринга, начав работу на пустой ленте?" неразрешима.

0.4.17. Покажите, что проблема определения того, является ли высказывание теоремой в исчислении высказываний, разрешима. Указание: См. упр. 0.3.2 и 0.3.3.

0.4.18. Покажите, что проблема выяснения, входит ли цепочка в данное рекурсивное множество, разрешима.

0.4.19. Существуют ли решающие последовательности для следующих частных случаев проблемы соответствий Поста:

(а) (01, 011), (10,000), (00,0);

(б) (1.11), (11,101), (101,011), (Oil, 1011)?

Как согласовать возможность ответа в этом упражнении с фактом неразрешимости проблемы соответствий Поста?

0.4.20. Покажите, что проблема соответствий Поста над алфавитом {а} разрешима. Как согласовать этот результат с неразрешимостью проблемы соответствий Поста над алфавитом, содержащим больше символов?

*0.4.21. Пусть Pj, Р, ...-перечень (нумерация) всех частичных алгоритмов в некотором формализме. Определим новый перечень Р[, Р, •-. следующим образом;

. (1) Пусть Paii - i-й ие всюду определенный алгоритм из

списка Pj, Яз, ... .

(2) Пусть Рс - -й (всюду определенный) алгоритм из списка

Р Р

Тогда существует простой алгоритм определения по данному /, является ли Р} алгоритмом: достаточно посмотреть, четно или нечетно число /. Более того, каждый Р,- совпадает с некоторым Pf. Как согласовать существование такого взаимно однозначного соответствия между натуральными числами и частичными алгоритмами с результатом примера 0.19? **0.4.22. Докажите неразрешимость проблемы соответствий Поста. Указание: Для данной машины Тьюринга постройте такой частный случай проблемы Поста, что решающая последовательность для него существует тогда и только тогда, когда эта машина Тьюринга останавливается, начав работу на пустой ленте.

*0.4,23. Покажите, что алгоритм Евклида из примера 0.15 останавливается не более, чем через AlogQ шагов, если начинает работу с такими входами р что q>\.

Определение. Вариантом проблемы соответствий Поста является проблема частичного соответствия над алфавитом 2. Эта проблема состоит в том, чтобы для любого данного конечного множества пар нз 2"" X 2+ определить, существует ли для каждого m > О такая последовательность не обязательно различных зр (и Уг), iit У-i), • • •. {т> Ут)* что первые т символов депочкн X-iX... совпадают с первыми т символами цепочки уу .., y„.

**0.4.24. Докажите, что проблема частичного соответствия неразрешима.

Замечания по литературе

Дэвис [1965] собрал хорошую аитолигию многих ранних работ по теории алгоритмов. Рабата Тьюринга [1936], в которой впервые появились машины Тьюриига, читается с особым интересом, если иметь в виду, что она написана До того, как были придуманы современные электронные вычислительные машины.

Исследование рекурсивных и частично-рекурсивных функций составляет часть теперь уже очень развитой области математики, называемой теорией




1ример ориентированного графа.

) См. также книгу Мальцева [1965].-Прим. перев.

Пара [а, b)R называется дугой (или ребром) графа G. Говорят, что дуга выходит из вершины а и входит в вершину Ь. Например, (1, 2)-дуга приведенного выше графа. Если (л, - дуга, то говорят, что вершина а предшествует вершине Ь, а вершина b следует за вершиной а.

Не вполне точно можно сказать, что два графа равны, если их можно изобразить одинаково, пренебрегая именами (обозна-чения.ми) вершин. Формально равенство неупорядоченных ориентированных графов определяется следующим образом.

Определение. Пусть G, (Л, и G2 = {A, /а) -графы. Будем говорить, что Gi и Gg равны (или изоморфны), если существует такое биективное отображение /: -Л, что aRb тогда и только тогда, когда f {а) RJ {Ь). Иначе говоря, в графе G из вершины а в вершину b ведет дуга тогда и только тогда, когда в графе из вершины, соответствующей а, ведет дуга в вершину, соответствующую Ь.

Часто вершинам и/или дугам графа приписывают некоторую информацию. Мы будем называть такую информацию разметкой, а соответствующий граф-помеченным графом.

Определение. Пусть (Л, R) - граф. Разметкой графа называется пара функций f и g, где / {разметка вершин) отображает Л в некоторое множество, а g {разметка дуг) отображает R в некоторое (возможно, Отличное от первого) множество. Пусть Gi = {Ai,Ri) и G2(Л2, R) - помеченные графы) с разметками (/i> и {fi, g) соответственно. Тогда Gj и Gg-равные помеченные графы, если существует такое биективное отображение h: Л-Ла, что

(1) aRb тогда и только тогда, когда h{a) RJi{b) (т. е. G и равны как непомеченные графы);

(2) {а) = /з {h {а)) (т. е. соответствующие вершины имеют одинаковые метки);

(3) 1 ((, &)) = 2 (( ()> ())) (т. е. соответствующие дуги имеют одинаковые метки).

Во многих случаях метками снабжаются только вершины или только дуги. В такой ситуации считается, что множество значений функции / или соответственно g состоит из единственного элемента. Тогда условие (2) или соответственно (3) выполняется тривиальным образом.

Пример 0.22. Пусть G-{{a, b, с], {{а, Ь), {Ь,с), {с, а)}) и G2 = ({0, 1,2}, {(1,0), (2, 1), (0,2)}). Разметка графа G, опреде-

) Говорят еще: нагруженные графы. - Прим. перев.

рекурсинных функций. Хорошие источники в этой области-книги Роджерса [191)7], Клини [19521 и Дэвиса [19581 1).

Проблема соответствий Ппст,ч enepnfje появилась в [Пост, 1947. Проблема частичного соответствия, сформулированная перед упр. 0.4.24, взята т [Кнут, 1965]-

Ис-стедовапне ложности внчислениГ! -это изучение алгоритмов с точки зрения измерения ч-исла элементарных операций (пременная сложность) или объема вспомогательной памяти (емкостная саожность), требуемых для вычисления данной функции. Бородин [1970J и Хартманис и Хопкрофт (1970] написали хоринше обзоры по эт теме, а Эрланд и Фишер [1970 составили библиографию.

Решения многих упражнений данного раздела, отмеченных звездочками, можно найти в книгах Минского [19G7] и Хопкрофта и Ульмана [1969],

0.5. НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Многие структуры, полезные при выполнении вычислений, удобно описывать с помощью графов и деревьев. В этом разделе мы рассмотрим ряд понятий теории графов, которые нам понадобятся в дальнейшем.

0,5.1. Ориентированные графы

Графы могут быть ориентированные н неориентированные, упорядоченные и неупорядоченные. Нас будут интересовать главным образом упорядоченны.е и неупорядоченные ориентированные графы.

Определение. Неупорядоченный ориентированный граф G -это пара (Л, R), где Л -множество элементов, называемых вершинами (или узлами), а R - отношение на множестве Л. Если не оговорено противное, термин граф будет обозначать ориентированный граф.

Пример 0.21. Пусть С-(Л, R), гдеЛ2, 3, 4} и R{{1, I), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}. Можно изобразить этот граф, занумеровав четыре точки числами J, 2, 3, 4 и проведя стрелку из точки а в точку Ь, если {a,b]R (рис. 0.6). □





Рис. 0.7. Равные помеченные графы.

Gi И G равны. Соответствующее биективное отображение h определяется формулами= О, ft (6)-2, ft(c)l. □

Определение. Последовательность вершин (г, а, ... ,а„), п1, называется путем (или маршрутом) длины п из вершины а в вершину а„, если для каждого 1 in существует дуга, выходящая из вершины а - и входящая в вершину а,-. Например, (1, 2, 4, 3)-путь в графе Gj, изображенном на рис. 0.6. Если существует путь из вершины в вершину то говорят, что а достижима из а.

Циклом называется путь [а, а, ...,а„), в котором аа. В графе на рис. 0.6 есть цикл (1, 1) длины 1 и цикл (1,2,4, 1) длины 3.

Граф называется сильно связным, если для любых двух разных вершин а и b существует путь яз а в Ь.

Введем, наконец, понятие степени вершины. Степенью по входу вершины а назовем число входящих в нее дуг, а степенью по выходу-число выходящих из нее дуг.

0.5.2. Ориентированные ациклические графы

Определение. Ациклическим графом называется (ориентированный) граф, не имеющий циклов. На рис. 0.8 показан пример ациклического графа.

Вершину, степень по входу которой равна О, назовем базовой. Вершину, степень по выходу которой равна О, назовем листом (нли концевой вершиной). На рис. 0.8 вершины 1,2,3 и 4 - базовые, а вершины 2, 4, 7, 8 и 9-листья.

Если (а, Ь)-дуга ациклического графа, то а называется п/?я-мым предком Ь, а b - прямым потомком а.

Если в ациклическом графе существует путь т ав Ь, то говорят, что а-предок Ь, а b - потомок а. На рис. 0.8 вершина 9-потомок вершины I, вершина 1-предок вершины 9.


©

Рис. 0.8. Пример ацикличе<жого графа.

Заметим, что если R - частичный порядок на множестве А, то (Л, /?) -ациклический граф. Более того, если {А, R) - ациклический граф и R - отношение „являться потомком", определенное на А, то R - частичный порядок на А.

0.5.3. Деревья

Дерево-это ациклический граф специального типа, имеющий много приложений в теории компиляторов.

Определение. (Ориентированным) деревом Т называется (ориентированный) граф G=(i4, R) со специальной вершиной гА, называемый корнем, у которого

(1) степень по входу вершины г равна О,

(2) степень по входу всех остальных вершин дерева Т равна 1,

(3) каждая вершина аА достижима из г.

На рис. 0.9, а изображено дерево с шестью вершинами. Корень обозначен числом I. Рисуя деревья, мы будем помещать корень вверху и направлять все дуги вниз. Приняв это соглашение, мы ;Не будем указывать стрелки.

Теорема 0.3. Дерево Т обладает следуюищми свойствами:

(1) Т-ациклический граф,

(2) для каждой вершины дерева Т существует единственный путь, ведуиий из корня в эту вершину.

Доказательство. Упражнение. □

Определение. Поддеревом дерева Т = {А, R) называется любое дерево Т" = (Л,/?), у которого

ляется формулами (а) [Ь) = X, {с) = У, ({а, Ь)) = gi{{b, с))а, g{{c, а)) = . Разметка графа определяется формулами f,{0) = fA)=X, fA)-y, 2((0. 2))-,((2, 1))-а, 2((i,0)) = p. Графы Gi и показаны на рис. 0.7.





0 1 2 3 4 5 6 [7] 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.002