Universal Sleptsov net. Issue 12 (2nd December 2017)

• Record Type: Journal Article
• Authors: Zaitsev, Dmitry A.
• Is Part Of: International journal of computer mathematics. Volume 94:Issue 12(2017)
• Page Start: 2396
• Page End: 2408
• Publication Date: 2017-12-02
• Subjects: Universal Sleptsov net -- Petri net -- Turing machine -- multiple firing -- polynomial complexity; 68Q05 -- secondary 65Y05; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2017.1283410
• Languages: English
• ISSNs: 0020-7160

Abstract

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.