Сеть Петри с дугой сброса

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

Известно, что класс сетей Петри, имеющих хотя бы одну дугу сброса, строго более выразим, чем обычные сети Петри.

In their 1977 статья Тоширо Араки и Тадао Касами доказали путем сведения автоматов-счетчиков Минского (см. теорему 5) к сетям Петри с дугами сброса, что проблема достижимости для сетей Петри с дугами сброса неразрешима.

А в 1981 году Эрнст Майр представил алгоритм решения проблемы достижимости обычных сетей Петри.

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

Процитированные выше документы требуют некоторых технических знаний для чтения, чего обычно не ожидают от студентов, изучающих CompSci. В качестве фона по этому вопросу я бы предложил оригинальную книгу «Вычисления: конечные и бесконечные машины» М.Л. Минский или любой современный вводный текст по логике в компьютерных науках.