Cтраница 2
Рабин был неверно упомянут в [148] как доказавший, что задача эквивалентности для множеств достижимости является неразрешимой, тогда как фактически он показал только, что задача включения неразрешима. Это доказательство не было опубликовано, но в 1972 году на совещании в МТИ было представлено новое доказательство. Оно приведено в данной работе, чтобы показать, что задача включения неразрешима. В нем используется десятая проблема Гильберта, которая сводится к недетерминированным регистровым машинам, которые в свою очередь эквивалентны сетям Петри. Это доказательство является основой доказательстваЦнеразрешимости задач эквивалентности и подмножества для множеств достижимости сети Петри, приведенных в гл. [16]