Universal Sleptsov net

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

AMS Subject Classifications:

• 68Q05
• secondary 65Y05

Acknowledgements

The author would like to thank Fred Baker and Richard Clegg for their help in improving the readability of the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

ORCID

Dmitry A. Zaitsev http://orcid.org/0000-0001-5698-7324