When Petri-nets were introduced to me, they were being described explicitly as a type of model that is not Turing-complete. While this might be true, I will prove in this article that a slightly generalized form of Petri-nets which allows for infinitely many places and infinitely many transitions is Turing-complete.
In this relatively short prerequisite for my longer article on the computational power of Petri-nets, I’ll be discussing Boolean pairs, a technique for simulating Boolean algebra with Petri-nets.