Cand. Sci. (Phys.-Math.), senior researcher, Department of Computational Mathematics and Cybernetics
кандидат физико-математических наук, старший научный сотрудник, факультет вычислительной математики и кибернетики
Dr. Sci. (Phys.-Math.), Professor, Department of Computational Mathematics and Cybernetics
доктор физико-математических наук, профессор, факультет вычислительной математики и кибернетики
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.
Статья посвящена описанию новой вариации стохастических блочных клеточных автоматов – так называемых марковских автоматов, отличительной особенностью которой является динамическое и стохастическое формирование блоков. Приводятся примеры простейших моделей физических процессов, построенные на основе такого типа автоматов. В статье рассматриваются выразительные возможности введенной модели. В частности, через сравнение с машиной Тьюринга показывается алгоритмическая универсальность марковских автоматов, что позволяет им теоретически выполнять сколь угодно сложную обработку символьных цепочек. С другой стороны, наличие в системе правил автомата так называемой перемешивающей подсистемы подстановок приводит к другому типу поведения данных автоматов, динамика которого описывается классическими кинетическими уравнениями для систем химических реакций. Показывается, что использование в автомате специальных разделительных символов (мембран) позволяет комбинировать в разных частях одного и того же автомата несколько различных типов поведения, а также организовывать информационное взаимодействие между этими частями. Данный прием открывает возможность моделирования простейших биологических систем – клеток. На примере двумерного варианта предлагаемой модели показывается, как можно расширить базовую одномерную модель на случай большей размерности.