Abstract
Motivation for new models of hyper-computations was presented. Sleptsov net was introduced compared to Petri and Salwicki nets. A concept of universal Sleptsov net, as a prototype of a processor in Sleptsov net computing, was discussed. Small universal Sleptsov net that runs in polynomial time was constructed; it consists of 15 places and 29 transitions. Principles of programming in Sleptsov nets, as composition of reverse control flow and data, have been developed. Standard control flow patterns include sequence, branching, loop, and parallel execution. Basic modules, which implement efficiently copying, logic, and arithmetic operations, have been developed. Special dashed arcs were introduced for brief specification of input and output data of modules (subnets). Ways of hierarchical composition of a program via substitution of a transition by a module were discussed. Examples of Sleptsov net programs for data encryption, fuzzy logic, and partial differential equations have been presented. Enterprise implementation of Sleptsov net programming promises ultra-performance.
TopBackground
A concept of algorithm was formalized for the first time by Alan Turing in 1936 in the form of an abstract machine which is traditionally called a Turing machine. Universal Turing machine which runs a given Turing machine is considered a prototype of a traditional computer. Besides Turing machines, other computationally universal systems appeared: recursive functions of Kleene, normal algorithms of Markov, tag rewriting systems of Post, register machines of Minsky. Variety of models is explained by controversial requirements of manifold application areas. Recent models employ facilities of massively parallel computations even in such simple constructs as elementary cellular automata which universality was proven in 2004 by Mathew Cook. Besides, smallest universal Turing machines were constructed in 2008 by Turlough Neary and Damien Woods which run in polynomial time. However, the way of programming cellular automata after Mathew Cook does not reveal their ability for massively parallel computing. Sleptsov net concept (Zaitsev, 2016) mends the flaw of Petri nets (Murata, 2013), consisting in incremental character of computations, which makes Sleptsov net computing (Zaitsev, 2014a; Zaitsev & Jürjens, 2016) a prospective approach for ultra-performance concurrent computing. In Zaitsev (2016), an overview of works, which refer to Sleptsov nets (Petri nets with multichannel transitions or multiple firing strategy), is presented.
Key Terms in this Chapter
Salwicki Net: A place-transition net where the maximal set of firable transitions fires at a step – maximum firing strategy.
Petri Net: A place-transition net where one transition fires at a step.
Sleptsov Net: A place-transition net where a transition fires at a step in a few copies – multiple firing strategy.
Turing Machine: An abstract machine consisting of infinite tape and a control head; was introduced by Alan Turing in 1936 as a formalization of the algorithm concept.
Algorithm: A declaration of a stepwise process of computations; the order of steps precisely prescribed; at each step exactly known how to obtain a result from the source date.
Computationally Universal System: A system capable to execute (run) a given algorithm.
Place-Transition Net: A directed bipartite graph with a dynamic process defined on it.