On simulating Turing machines with inhibitor Petri nets
Dmitry A. Zaitsev, Zonghui Li · IEEJ Transactions on Electrical and Electronic Engineering · 2017
An inhibitor Petri net is constructed that simulates an arbitrary given Turing machine. The tape of the Turing machine, its program, and internal states are encoded by the marking of nine dedicated places of the Petri net. The rules of Turing machine work are encoded by a single control flow represented by a token passage within the inhibitor Petri net composed of the sequence, branch, and loop operators. Subnets that implement arithmetic, comparison, and copying operations are employed. In the Petri net paradigm of computation, a Petri net that simulates Turing machines provides the compatibility of concepts. It is a prototype of a co‐processor supplementary to the basic processor of Petri nets. © 2017 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.