Toward the Minimal Universal Petri Net

A universal Petri net with 14 places, 42 transitions, and 218 arcs was built in the class of deterministic inhibitor Petri nets (DIPNs); it is based on the minimal Turing machine (TM) of Woods and Neary with 6 states, 4 symbols, and 23 instructions, directly simulated by a Petri net. Several techniques were developed, including bi-tag system (BTS) construction on a DIPN, special encoding of TM tape by two stacks, and concise subnets that implement arithmetic encoding operations. The simulation using the BTS has cubic time and linear space complexity, while the resulting universal net runs in exponential time and quadratic space with respect to the target net transitions' firing sequence length. The technique is applicable for simulating any TM by the Petri net.