Simulating Cellular Automata by Infinite Petri Nets
Dmitry A. Zaitsev
We construct a series of infinite Petri nets which directly simulate the elementary cellular automaton Rule 110; the nets run either in synchronous or asynchronous way and also differ in whether they use extensions such as inhibitor and read arcs. For finite specification of infinite nets, parametric expressions are employed. The synchronous nets are arranged as an infinite repetition of a block consisting of (1,2), (2,2), or (7,7) places and transitions, when using both inhibitor and read arcs, read arcs only, or no extended arcs, respectively. A classical (asynchronous) Petri net is constructed which simulates the elementary cellular automaton Rule 110 via expanding traversals of the cell array using a cell model consisting of (9,12) places and transitions, respectively. The constructed nets simulate the cellular automaton in polynomial time. Based on known results we conclude that these Petri nets are Turing-complete; this proves universality of infinite classical (asynchronous) Petri nets. Generalizations of the presented simulation technique on various classes of cellular automata (multidimensional, totalistic, asynchronous etc) are discussed.
Keywords: Universal Petri net, infinite Petri net, cellular automata, Turing machine, simulation, complexity