Чтобы убедиться в этом, достаточно показать неразрешимость более узкой проблемы, а именно - не существует ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Котов В.Е. Сети Петри


Чтобы убедиться в этом, достаточно показать неразрешимость более узкой проблемы, а именно - не существует алгоритма, который для любого счетчика может установить, будет ли его начальное нулевое значение изменено хотя бы один раз, т.е. является ли счетчик 0-ограниченным или нет. Введем дополнительный вспомогательный счетчик х, запись в который делается только после того, как исходный автомат останавливается, выполнив заключительный оператор стоп. Для этого достаточно заменить этот оператор на последовательность операторов ж: х 1 и стоп. Если бы была разрешима проблема 0-ограниченности, то мы могли бы решать проблему остановки счетчикового автомата, воспользовавшись описанным преобразованием. Таким образом, проблема Оюграниченность не может быть разрешимой и, следовательно, неразрешима более общая проблема ограниченности счетчиков и проблема ограниченности ингибиторной сети.

(cкачать страницу)

Смотреть книгу на libgen

Чтобы убедиться в этом,  достаточно показать неразрешимость более узкой проблемы,  а именно  -  не существует алгоритма,  который для любого счетчика может установить,  будет ли его начальное нулевое значение изменено хотя бы один раз,  т.е. является ли счетчик 0-ограниченным или нет.  Введем дополнительный вспомогательный счетчик х,  запись в который делается только после того,  как исходный автомат останавливается,  выполнив заключительный оператор стоп.  Для этого достаточно заменить этот оператор на последовательность операторов ж:   х 1 и стоп.  Если бы была разрешима проблема 0-ограниченности,  то мы могли бы решать проблему остановки счетчикового автомата,  воспользовавшись описанным преобразованием.  Таким образом,  проблема Оюграниченность не может быть разрешимой и,  следовательно,  неразрешима более общая проблема ограниченности счетчиков и проблема ограниченности ингибиторной сети.