Universal Sleptsov net |
| |
Authors: | Dmitry A. Zaitsev |
| |
Affiliation: | Department of Computer Engineering and Innovation Technology, International Humanitarian University, Odessa, Ukraine |
| |
Abstract: | We construct a universal Sleptsov net (USN) with 13 places and 26 transitions that runs in polynomial time; a Sleptsov net is a place-transition net that allows multiple instances of transition firing within a single step. We simulate Neary and Woods’ small weakly universal Turing machine with two states and four symbols. Compared to previous results, we do not use separate encoding and decoding subnets, which implement such operations as: multiplication by a constant combined with addition and division by a constant combined with modulo, respectively, but overlap them in a special way that reduces the number of USN nodes by four. Besides, we present a thorough analysis of the source data encoding complexity. The obtained universal net is a prototype of a processor in the SN paradigm of computing that promises hyper-performance. |
| |
Keywords: | Universal Sleptsov net Petri net Turing machine multiple firing polynomial complexity |
|
|