Abstract:
The article is devoted to the description of a new variation of stochastic block cellular automata – the so-called Markov automata, a distinctive feature of which is the dynamic and stochastic formation of blocks. Examples of the simplest models of physical processes built on the basis of this type of automata are given. The expressive possibilities of the introduced model are considered in the article. In particular, through comparison with the Turing machine, the algorithmic universality of Markov automata is shown, which allows them to theoretically perform arbitrarily complex processing of symbol chains. On the other hand, the presence of the so-called mixing substitution subsystem in the system of automata rules leads to a different type of behavior of these automata, the dynamics of which is described by classical kinetic equations for chemical reaction systems. It is shown that the use of special separating symbols (membranes) in the automaton allows combining several different types of behavior in different parts of the same automaton, as well as organizing information interaction between these parts. This technique opens up the possibility of modeling the simplest biological systems – cells. Using the example of a two-dimensional version of the proposed model, it is shown how the basic one-dimensional model can be extended to the case of higher dimensions.
Fulltext:
PDF file (105507 kB)