5.5.  Неразрешимые задачи

В предыдущем разделе мы показали, что многие задачи достижимости и активности эквивалентны, но никакого результата относительно разрешимости этих задач еще не получили. Для того чтобы показать разрешимость, необходимо свести задачу для сетей Пеіри к задаче с известным решением, а для того, чтобы показать неразрешимость, нужно свести задачу, которая известна как неразрешимая, к задаче для сетей Петри. Первый важный результат такого рода был получен Рабином [26]. Он показал неразрешимость задачи: выполняется ли R(Clt р2) для двух сетей Петри —

Cj с маркировкой pt и С2 с маркировкой р2? Позднее Хэк [114] показал, что неразрешимой является и задача: выполняется ли R(Ci, pj) = R(C2, р2)? Доказательство этих утверждений основано на десятой проблеме Гильберта. (Д. Гильберт на конференции математиков в 1900 г. поставил 23 проблемы, и та, на которую опирался Хэк, была десятой в списке)

Определение 5.9. Дан полином Р от п переменных с целыми коэффициентами; существует ли такой вектор целых (хи х2, хп), что Р{хі, х2, хп) =■ 0? Уравнение Р{хи х2, ..., хп) = 0 называется диофантовым.

В общем оно представляет собой сумму членов:

Диофантовыми уравнениями являются xt = 0; 3xt ■ х2 + 6л:3 = = 0 и т. д.

В 1970 г. Матиясевич|> доказал, что десятая проблема Гильберта неразрешима [70, 711: не существует общего алгоритма, определяющего, имеет ли произвольное диофантово уравнение корень (набор значений, для которых полином равен нулю). Этот результат служит основой доказательства того, что задача равенствг множеств достижимости сетей Петри неразрешима. Стратегия егс заключается в построении для диофантова полинома сети Петри которая (в определенном смысле) вычисляет все значения поли нома.