Пред.
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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
5.5. Неразрешимые задачиВ предыдущем разделе мы показали, что многие задачи достижимости и активности эквивалентны, но никакого результата относительно разрешимости этих задач еще не получили. Для того чтобы показать разрешимость, необходимо свести задачу для сетей Петри к задаче с известным решением, а для того, чтобы показать неразрешимость, нужно свести задачу, которая известна как неразрешимая, к задаче для сетей Петри. Первый важный результат такого рода был получен Рабином [26]. Он показал неразрешимость задачи: выполняется ли Определение 5.9. Дан полином В общем оно представляет собой сумму членов:
Рис. 5.8. Сведения, показывающие, что задача равенства (и подмножества) длямножеств достижимости сетей Петри неразрешима. Диофантовыми уравнениями являются В 1970 г. Матиясевич доказал, что десятая проблема Гильберта неразрешима [70, 711: не существует общего алгоритма, определяющего, имеет ли произвольное диофантово уравнение корень (набор значений, для которых полином равен нулю). Этот результат служит основой доказательства того, что задача равенства множеств достижимости сетей Петри неразрешима. Стратегия его заключается в построении для диофантова полинома сети Петри, которая (в определенном смысле) вычисляет все значения полинома. 5.5.1. Задача включения графов полиномовДоказательство неразрешимости задачи равенства состоит из трех частей (рис. 5.8). Сначала десятая проблема Гильберта сводится к задаче включения графов полиномов. Затем задача включения графов полиномов сводится к задаче подмножества для множеств достижимости сетей Петри. Наконец, задача подмножества для множеств достижимости сетей Петри сводится к задаче равенства множеств достижимости сетей Петри. Это показывает, что десятая проблема Гильберта, известная как неразрешимая, сводится к задаче равенства, которая поэтому также должна быть неразрешимой. Определение 5.10. Граф
Определение 5.11. Задача включения графов полиномов заключается в определении для двух диофантовых полиномов Покажем сначала, что десятая проблема Гильберта сводится к задаче включения графов полиномов. Теорема 5.8. Задача включения графов полиномов неразрешима. Доказательство: 1. Ограничим наше доказательство задачами с неотрицательными решениями. Если 2. Аналогично, поскольку 3. Сейчас можно разбить любой полином 4. Рассмотрим два графа полиномов:
Теперь
Но из п. 3 следует, что
что справедливо тогда и только
5. Итак, для определения того, что уравнение 5.5.2. Слабое вычислениеТеперь нам необходимо показать, что сети Петри могут (в определенном смысле) вычислять значение полинома Эта сеть Петри слабо вычисляет значение Сейчас мы хотим показать, что можно построить подсеть, слабо вычисляющую функцию умножения (двух чисел). На ее основе мы можем построить составную сеть, которая слабо вычисляет значение каждого члена полинома путем последовательной композиции подсетей умножения. Выход подсети для каждого члена будет помещаться в выходную позицию для полинома. Таким образом, число фишек в выходной позиции будет суммой выходов для каждого члена. Подсеть умножения показана на рис. 5.10. Эта сеть слабо вычисляет произведение чисел х и у, представимых фишками в ее входных позициях, помещая множество фишек в свой выход. Действует сеть совсем просто.
Рис. 5.9. Базовая структура сети Петри, слабо вычисляющей значение полинома Для вычисления произведения х и у сначала запускается переход Мы описали наилучший случай в том смысле, что число выходных фишек в точности равно Рис. 5.10. (см. скан) Подсеть умножителя. Эта подсеть слабо вычисляет произведение х и у. гарантировать, что число фишек в Далее на рис. 5.12 показано, как можно слабо вычислять полином Теперь для создания конкретных необходимых множеств достижимости вводится несколько управляющих переходов и позиций. Сначала необходимо обеспечить получение произвольного значения для каждой из переменных Рис. 5.11. (см. скан) Сеть Петри, слабо вычисляющая член диофантова уравнения. Каждый блок в сети имеет вид, изображенный на рис. 5.10. позиции Эти переходы могут запускаться произвольное число раз, создавая любые значения в Рис. 5.12. (см. скан) Сеть Петри, слабо вычисляющая Для сведения задачи включения графов полиномов к задаче подмножества выполним следующие шаги. Пусть мы хотим определить для полиномов А и 5, выполняется ли 1. Построим сеть Петли 2. Если число позиций в этих сетях не равно, добавим позиции в ту сеть, где их меньше с тем, чтобы уравнять число позиций. Эти позиции не имеют начальной маркировки и не связаны с какими-либо переходами в сети. 3. Теперь мы должны устранить влияние всех внутренних позиций на множества достижимости. И в неважна. Однако может оказаться, что для внутренней позиции Для того чтобы обойти это препятствие, введем по две новые позиции: Один из этих переходов, вводимых для каждой внутренней позиции 4. Описанная конструкция показана на рис. 5.13. Для двух сетей Петри
Рис. 5.13. Сеть Петри, построенная для проверки включения графов полиномов. Следовательно, если Таким образом, мы показали справедливость следующего. Теорема 5.9. Задача включения графов полиномов сводима к задаче подмножества для множеств достижимости сетей Петри. Доказательство взято из [114, 116]. 5.5.3. Задача равенстваТеперь нам осталось только показать, что задача подмножества для множеств достижимости сетей Петри сводится к задаче равенства. Предположим, что имеются две сети Петри А и 5, и Рис. 5.14. (см. скан) Построение сетей Петри Конструкция иллюстрируется рис. 5.14. Позиции Далее вводятся еще одна позиция свою начальную маркировку, и все ее переходы могут запускаться, как обычно, поскольку в
или любая последовательность вида
Сеть Сеть Рассмотрим теперь множества достижимости сетей Петри
Сеть Петри
Сеть Петри
Теперь, если Таким образом, на основе этой конструкции доказано следующее. Теорема 5.10. Задача подмножества для множеств достижимости сетей Петри сводима к задаче равенства для множеств достижимости сетей Петри. Последние три теоремы приводят к следующему результату. Теорема 5.11. Следующие задачи неразрешимы: 1. Задача включения графов полиномов. 2. Задача подмножества для множеств достижимости сетей Петри. 3. Задача равенства для множеств достижимости сетей Петри. Эти теоремы и их доказательства принадлежат Хэку [114, 116].
|
1 |
Оглавление
|