7.3. Расширенные сети Петри и регистровые машины

Мы показали, что все предложенные расширения модели сетей Петри допускают возможность проверки позиции на нуль. Насколько это важно по отношению к мощности разрешения сетей Петри? Влияет ли это на возможность анализа сетей Петри?

Проверка на нуль уменьшает мощность разрешения сети Петри. Агервала [4], Хэк [115], Томас [290] и др. показали, что появление способности проверки на нуль у модели сетей Петри позволяет

сетям Петри моделировать машину Тьюринга. Таким образом, сети Петри с проверкой на нуль дают схему моделирования, с помощью которой можно моделировать любую систему. Однако почти все вопросы анализа сетей Петри становятся неразрешимыми, поскольку они неразрешимы для машин Тьюринга.

Доказательство эквивалентности расширенных сетей Петри и машин Тьюринга относительно просто. Легче всего его представить в терминах регистровых машин Шепардсона и Стургиса [276] или программных машин Минского [200].

Регистровая машина есть абстрактная модель ЭВМ с несколькими регистрами, которые используются для хранения произвольно больших чисел. Для манипулирования этими регистрами пишется программа. Программа есть последовательность инструкций вида «увеличить регистр на 1», «уменьшить регистр на 1 (только если регистр не равен «перейти к предложению если регистр не равен нулю», и т. д. Ниже представлена программа сложения содержимого регистра 2 с регистром 1.

1. Если регистр 2 равен нулю, то идти к инструкции 5.

2. Вычесть 1 из регистра 2.

3. Прибавить 1 к регистру 1.

4. Идти к инструкции 1.

5. Стоп.

Шепардсон и Стургис показали, что регистровая машина со следующими инструкциями эквивалентна машине Тьюринга.

1. увеличить регистр на 1.

2. уменьшить регистр на 1 (регистр не равен нулю).

3. перейти к предложению если регистр равен нулю. Таким образом, если регистровая машина может быть преобразована в эквивалентную сеть Петри, то тем самым будет показано, что расширенные сети Петри эквивалентны регистровым машинам. Это преобразование относительно просто.

Для представления регистровой машины расширенной сетью Петри представим регистров, используемых в программе, позициями Мы также используем позицию для представления положения счетчика инструкций либо перед предложением 1 (начальная маркировка), либо после предложения для В программе из предложений. Каждая инструкция в программе представляется переходом. На рис. 7.12 показано, как каждая из трех вышеприведенных инструкций представляется переходом в расширенной сети Петри. Из этого видно, что регистровая машина может быть преобразована в расширенную сеть Петри, и, следовательно, расширенная сеть Петри эквивалентна машине Тьюринга. Эта эквивалентность машине Тьюринга разрушает все надежды на возможность анализа расширенных сетей Петри. Однако это же доказывает, что расширенные сети Петри могут моделировать любую систему (или по крайней мере любую вычислимую систему). Таким образом, мы видим, что увеличение мощности

Рис. 7.12. (см. скан) Преобразование инструкции регистровой машины в переход расширенной сети Петри со сдерживающими дугами. а увеличить содержимое регистра на 1; уменьшить содержимое регистра на 1 (содержимое регистра должно быть положительным); в — переход к инструкции в случае нулевого значения регистра

моделирования в этом случае приводит к определенному уменьшению мощности разрешения.

Отметим также, что ключевым моментом в доказательстве эквивалентности сетей Петри, регистровых машин и машин Тьюринга является способность к проверке одной позиции на нуль. Таким образом, все предложенные расширения — области ограничения, переходы исключающее ИЛИ, переключатели, приоритеты, интервалы времени и сдерживающие дуги — расширяют модели сетей Петри до уровня машин Тьюринга.

Существуют другие предложения по расширению, которые не поднимают сети Петри до уровня машин Тьюринга. Первыми в качестве расширений были предложены петли и кратные входные и выходные дуги. Но как это было показано в разд. 5.3, такие сети Петри фактически эквивалентны простым сетям Петри. Аналогично добавление входов ИЛИ, выходов ИЛИ, выходов исключающее ИЛИ не увеличило бы мощность моделирования сетями Петри.

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