Моделі клітинних автоматів з комплекснозначними функціями переходу
The new class of mathematical models for computation theory is considered — namely cellular automata (CA) with branching complex-valued transition functions. The key point is possible multivaluedness of cell’s states with such transition functions. Different cases with complex-value transition funct...
Збережено в:
| Дата: | 2020 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2020
|
| Теми: | |
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/228540 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866302727282229248 |
|---|---|
| author | Makarenko, Alexander |
| author_facet | Makarenko, Alexander |
| author_sort | Makarenko, Alexander |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2021-04-08T14:17:06Z |
| description | The new class of mathematical models for computation theory is considered — namely cellular automata (CA) with branching complex-valued transition functions. The key point is possible multivaluedness of cell’s states with such transition functions. Different cases with complex-value transition functions had been considered. Dynamics CA on one branch and on different isolated branches are described. Also the case of transitions of states between branches is proposed. The case of continuous-valued CA and their finite-valued approximations are discussed. The problem of approximation of multivalued CA is stated. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2020.4.11 |
| first_indexed | 2025-07-17T10:27:09Z |
| format | Article |
| fulltext |
Alexander Makarenko, 2020
Системні дослідження та інформаційні технології, 2020, № 4 141
TIДC
НОВІ МЕТОДИ В СИСТЕМНОМУ АНАЛІЗІ,
ІНФОРМАТИЦІ ТА ТЕОРІЇ ПРИЙНЯТТЯ РІШЕНЬ
UDC 519.925.51
DOI: 10.20535/SRIT.2308-8893.2020.4.11
CELLULAR AUTOMATA MODELS WITH COMPLEX VALUED
TRANSITION FUNCTIONS
A.S. MAKARENKO
Abstract. The new class of mathematical models for computation theory is consid-
ered — namely cellular automata (CA) with branching complex-valued transition
functions. The key point is possible multivaluedness of cell’s states with such transi-
tion functions. Different cases with complex-value transition functions had been
considered. Dynamics CA on one branch and on different isolated branches are de-
scribed. Also the case of transitions of states between branches is proposed. The
case of continuous-valued CA and their finite-valued approximations are discussed.
The problem of approximation of multivalued CA is stated.
Keywords: cellular automata, complex-valued transition functions, Riemann sur-
faces, continuous-valued CA, branching, approximation of multivaluedness, compu-
tations.
INTRODUCTION
Typically, classical cellular automatic machines (CA) have a cell assembly struc-
ture with a certain set of possible states. The states change at discrete points in
time according to certain rules. Up to now, as far as we know, these dynamic
rules have been defined using unambiguous transition functions. Recently, there
has been a need to investigate CA with multi-valued transition functions and mul-
ti-valued states of the cells [1, 2]. The multi-valued case is much more difficult
then single-valued case. Further study of such new CA (with multivaluedness)
depends on examining specific examples of such objects. In this paper, we pro-
pose complex-valued cellular automata with a branched (multi-valued) structure
with values on the Riemann surface. CA with the location of cells on the Riemann
surface is also considered. Using complex-valued CA allows using the rich set of
mathematical tools of complex-valued analysis.
So we propose the setting of many research problems in case of complex-
valued CA. The structure of the paper is the next. In the section 2 we give the
formal description of common cellular automata.
The section 3 is devoted to remembering some elements of complex-valued
analysis. One — dimensional case of CA is considered in section 4. There are
proposed many new problems for investigations. One of the main problems is ap-
proximation problem. Such problem is very important for approximate calculation
of multivalued solutions.
A.S. Makarenko
ISSN 1681–6048 System Research & Information Technologies, 2020, № 4 142
DESCRIPTION OF THE CELLULAR AUTOMATON
Here we give the formal description of cellular automata with anticipation. First
of all we follow the papers on CA (see for example [1–7]). We pose here the de-
scription one-dimensional CA from [1] but the description can be modified to
many-dimensional cases.
One-dimensional CA is represented by an array of cells ix where i (in-
teger set) and each x takes a value from a finite alphabet . Thus, a sequence of
cells }{ ix of finite length n represents a string or global configuration c on .
This way, the set of finite configurations will be represented as n . An evolution
is represented by a sequence of configurations }{ tc given by the mapping
nn : ; thus their global relationship is as follows:
1)( tt cс .
Where t time steps and every global state c of affairs are defined by a se-
quence of cell states. Also the cell states in configuration tc are updated at the
next configuration 1tc simultaneously by a local function as follow s’:
1),...,,...,(
t
i
t
ri
t
i
t
ri xxxx ;
— multi-valued complex function. Note that classical studies assume that an
unambiguous transition function [3–6]. At the same time, there may be various
variants of using branching complex-digit functions with Riemann surfaces. The
simplest cases are given here, which convey some of the behaviour of this class of
objects. Let us preliminarily recall the description of functions with Riemann sur-
faces.
RIEMANN SURFACES
Riemann’s hierarchy is the traditional name for one-dimensional complex differ-
entiable diversity in comprehensive analysis. Such surfaces were systematically
studied by Bernhard Riemann (Fig. 1, 2) Examples of Riemann surfaces include
the complex plane and sphere
of Riemann. The surface of
Riemann allows geometrically
to present multi-valued func-
tions of a complex variable in
such a way that each of its
points corresponds to one value
of multi-valued function, and
at continuous movement on
a surface the function also
changes continuously. The
canonical view of the Rie-
mann surface is the represen-
tation as a flatbread with
some number of holes [8–11].
1
0,5
0
–0,5
–1
1
0,5
0
–0,5
–1
1
0,5
0
–0,5
–1
Fig. 1. Riemann surface for the function zzf )(
Cellular automata models with complex valued transition functions
Системні дослідження та інформаційні технології, 2020, № 4 143
According to Felix Klein, the idea of the Riemann surface still belongs to
Galois: in his suicide letter he mentions some research on “ambiguity of func-
tions” among his achievements (Fig. 3) [11]. The topological characteristic of the
Riemann surface is the genus; the genus surface is a sphere, the genus surface is
a torus [8–11].
As an example, we also give the function of a complex variable with a single
branching point, for example
ONE-DIMENSIONAL CASE
In this paragraph we will illustrate the new research problems in the sim-
plest cases.
One branching point. One branching point where branching conditions are
not met for any point (e.g. all values during evolution are on the same branch of a
function, e.g. on a function branch. Then the branching point is the only point, but
let the CA values be outside the vicinity of the branching point. This corresponds
to the class of unambiguous CA, but with certain generalizations. Namely, in our
general case, CA looks like:
);}({1
N
nn
i xx ,
n
ix — state value of i cell at n moment of time ( ...,2,1,0n ). In the case of clas-
sic CA, such as a game of life, the state of the cell is 0 или 1. In our case, the
Fig. 2. Riemann surface for function zxf log)(
Fig. 3. Details of the construction of the Riemann surface function zzf )(
A.S. Makarenko
ISSN 1681–6048 System Research & Information Technologies, 2020, № 4 144
complex function , 1, CMMxn
i where M — some subset of the space of
complex numbers. Very conventionally, this can be represented in the form of
a figure (Fig. 4)
Here we represent the evolution of the values of one cell (Fig. 5). Other cells
in case without branching have the same qualitative evolution depending on initial
condition in the neighborhood of cell. Note that just in such case we have essen-
tial difference from the classical case. We can assume a whole set of values ,M
including Mcard , when a continuum of values is also allowed. (Remark that
in classical case }1,0{M . Note that in general case it is possible to consider
approximations of a continuum set M using a discrete set MM K with a finite
number K of possible cell values. This can be roughly seen in the figure
An interesting task is the rigorous mathematical study of the applicability of
such approximation, as well as the crystallization of the approximation.
An interesting task is the rigorous mathematical investigation of the applica-
bility of such approximation as well as questions of marginal behaviour over time.
Fig. 4. Evolution of one cell by one branch
f(x)
1
ix
n
ix
0
ix
2
ix
n n+1 n+2 t
Fig. 5. Using approximations in evolution
f(x)
n n+1 n+2 t
Cellular automata models with complex valued transition functions
Системні дослідження та інформаційні технології, 2020, № 4 145
It can be assumed that assigning a rule to the CA transition as an analytical func-
tion can simplify the investigation of such questions.
Case of branching of transition function. A more complicated case is when
the branching point of the transition function appears in the value range for only
one cell. An illustration of chiefs appearing in the value range for only one cell is
given in the figure below (Fig. 6).
A simpler case appears to be implemented for the function , presumably
with no jumps between branches, which requires further research. In this case, the
idea of approximation with a finite set of values by branches can also be applied.
However, for arbitrary analytical functions case may be exist with a large
number of branches (or even an infinite number of branches). In this case, all
studies on the limit behavior of CA remain valid. However, limit behavior must
be investigated for a multi-valued case, for which the theory of multi-valued dy-
namic systems should be involved [12]. Along the way, we will point out another
new class of research problems. For ordinary traditional cellular automata (includ-
ing the game of Life) we can set the following problem: according to the well-
known rules of CA, to find CA with a complex-valued transition function such
that traditional CA is an approximation of complex-valued CA.
In this case, it is possible to raise the problem of studying traditional CA.
Probably, the function can only evolve over two branches independently of
each other (without jumping from branch to branch). At the same time, in the case
of an arbitrary function it is possible and the situation with jumps between
branches is possible.
This creates a whole new set of problems associated with finding special
function . The first class of problems is related to the construction related to a
specific CA (including traditional ones). For some CA, it is possible to find the
exact function by deforming known complex functions. Another possibility is to
determine on the basis of known approaches from artificial intelligence: for ex-
ample, identification methods or machine learning. But, it may turn out that pre-
Fig. 6. General cases for an arbitrary transition function with possible dynamic transitions
between two branches
n n+1 n+2
f(x)
t
A.S. Makarenko
ISSN 1681–6048 System Research & Information Technologies, 2020, № 4 146
cise definition of a function is very resource-intensive or unconstructive. Then it
is necessary to simplify problem definition and achieve only the proximity of a
given CA solution with a certain complex function at a certain time range
[0, T]. Closely related to this is the question of the stability of the behaviour of
solutions to such approximation with a small change in function . It is also pos-
sible to use functions with an infinite number of branching points. It is also im-
portant to construct a function with given branching points so that these branching
points set a fixed behavior of the solution or at least approximate the required be-
havior of a multi-valued solution on a certain range.
The next class of tasks related to the selection of functionality for the task is
to build an algorithm for solving a particular task or with the theory of calcula-
tions. Note that possible links with quantum computing are viewed here. It is also
possible to introduce a special category of complex-valued CA with branches.
The problems above are easy to generalize for other problems as well. Thus,
nothing limits the transfer from the case of 1D space with only one branching
point in one cell to the case of possible branching points in each cell of the cell
space. Everything said above is carried over to the case of 2D, 3D, ND spaces.
But it is also possible to generalize the very concept of cellular automata. Thus, it
is possible to consider cell automata on Riemann surfaces. A particular problem is
the study of the dependence of the dynamics of CA on the topology of the space
in which CA is given.
By the way, the transition from CA with a continuum of possible values to
approximations of finite sets correlates with the study of continuous dynamical
systems with the methods of symbolic dynamics in ergodic theory.
CONCLUSIONS
Thus in proposed paper we had been introduced new class of cellular automata
with presumable multivaluedness. New research problems are proposed for such
cellular automata. The most important problem is the problem of approximation.
Also further more complex research problem are described including the investi-
gation of CA on the Riemann surfaces.
REFERENCES
1. A. Makarenko, “Multivaluedness in cellular automata with strong anticipation and
prospects for computation theory”, WSEAS Transactions on Information Science and
Applications, vol. 17, pp. 69–79, 2020.
2. A. Makarenko, “Cellular Automata with anticipation: Some new Research Prob-
lems”, Int. Journal of Computing Anticipatory Systems (Belgium), 20, pp. 230–242,
2008.
3. D. Krushinskiy and A. Makarenko, “Cellular automata with anticipation: examples
and presumable applications”, AIP Conference Proceedings (USA), vol. 1303,
pp. 246–254, 2010.
4. A. Illiachinski, Cellular Automata. A Discrete Universe. Singapore: World Scientific
Publishing, 2001.
5. S. Wolfram, New kind of science. USA: Wolfram Media Inc., 2002.
6. B. Chopard and M. Droz, Cellular Automata Modeling of Physical Systems. Cam-
bridge: Cambridge Univ. Press, 1998.
Cellular automata models with complex valued transition functions
Системні дослідження та інформаційні технології, 2020, № 4 147
7. L. Faccetti and A. Makarenko, “”Game of Life” with Modifications: Non-regular
Space, Different Rules and Many Hierarchical Levels”, Int. J. Information Content
& Processing, 4 (1), pp. 21–50, 2017.
8. V.V. Golubev, Lectures on analytical theory of differential equations [in Russian].
M.-L.: Gostekhteorizdat, 1941, 400 p.
9. A.I. Markushevich, Theory of analytical functions [in Russian]. М., 1967.
10. B.V. Shabat, Introduction to complex analysis. Publisher: Lan, 577 p. Available:
https://scask.ru/o_book_cmp.php?id=32.
11. Riemann_surfaces. Available: En/Wikipedia/Riemann_surfaces
12. M.Z. Zgurovsky and V.S. Melnik, Nonlinear analysis and control of physical
processes and fields. Springer Science&Business Media, 2012, 508 p.
Received 09.12.2020
INFORMATION ON THE ARTICLE
Alexander S. Makarenko, ORCID: 0000-0001-6728-3058, Educational and Scientific
Complex “Institute for Applied System Analysis” of the National Technical University of
Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, e-mail: makalex@i.com.ua
МОДЕЛІ КЛІТИННИХ АВТОМАТІВ З КОМПЛЕКСНОЗНАЧНИМИ
ФУНКЦІЯМИ ПЕРЕХОДУ / О.С. Макаренко
Анотація. Розглянуто новий клас математичних моделей для теорії обчис-
лень — клітинні автомати (КA) з розгалуженими комплекснозначними пе-
рехідними функціями. Ключовим моментом є можлива багатозначність станів
клітини з такими перехідними функціями. Розглянуто різні випадки
з перехідними функціями з комплексними значеннями. Описано динаміку КA
на одній гілці та на різних ізольованих гілках. Запропоновано розгляд випадку
переходів станів між гілками, а також випадку неперервнозначних КA та їх
кінцевозначних наближень. Поставлено проблему апроксимації багатознач-
них КА.
Ключові слова: клітинні автомати, комплекснозначні перехідні функції, по-
верхні Рімана, неперервнозначні КA, розгалуження, наближення багатознач-
ності, обчислення.
МОДЕЛИ КЛЕТОЧНЫХ АВТОМАТОВ С КОМПЛЕКСНОЗНАЧНЫМИ
ФУНКЦИЯМИ ПЕРЕХОДА / А.С. Макаренко
Аннотация. Рассмотрен новый класс математических моделей теории вычис-
лений — клеточные автоматы (КА) с ветвящимися комплекснозначными пере-
ходными функциями. Ключевым моментом является возможная многознач-
ность состояний клетки с такими переходными функциями. Рассмотрены
различные случаи с комплексными переходными функциями. Описана дина-
мика КA на одной ветке и на разных изолированных ветвях. Предложено рас-
смотрение случая переходов состояний между вервями, а также случая непре-
рывнозначных КА и их конечнозначных приближений. Поставлена
проблема аппроксимации многозначных КА.
Ключевые слова: клеточные автоматы, комплекснозначные переходные
функции, римановы поверхности, непрерывнозначные КА, ветвление, аппрок-
симация многозначности, вычисления.
|
| id | journaliasakpiua-article-228540 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2025-07-17T10:27:09Z |
| publishDate | 2020 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/6b/a09835b7393ed6da0af023cb5a6e5a6b.pdf |
| spelling | journaliasakpiua-article-2285402021-04-08T14:17:06Z Cellular automata models with complex valued transition functions Модели клеточных автоматов с комплекснозначными функциями перехода Моделі клітинних автоматів з комплекснозначними функціями переходу Makarenko, Alexander клітинні автомати комплекснозначні перехідні функції поверхні Рімана неперервнозначні КА розгалуження наближення багатозначності обчислення cellular automata complex-valued transition functions Riemann surfaces continuous-valued CA branching approximation of multivaluedness computations клеточные автоматы комплекснозначные переходные функции римановы поверхности непрерывнозначные КА ветвление аппроксимация многозначности вычисления The new class of mathematical models for computation theory is considered — namely cellular automata (CA) with branching complex-valued transition functions. The key point is possible multivaluedness of cell’s states with such transition functions. Different cases with complex-value transition functions had been considered. Dynamics CA on one branch and on different isolated branches are described. Also the case of transitions of states between branches is proposed. The case of continuous-valued CA and their finite-valued approximations are discussed. The problem of approximation of multivalued CA is stated. Рассмотрен новый класс математических моделей теории вычислений — клеточные автоматы (КА) с ветвящимися комплекснозначными переходными функциями. Ключевым моментом является возможная многозначность состояний клетки с такими переходными функциями. Рассмотрены различные случаи с комплексными переходными функциями. Описана динамика КA на одной ветке и на разных изолированных ветвях. Предложено рассмотрение случая переходов состояний между вервями, а также случая непрерывнозначных КА и их конечнозначных приближений. Поставлена проблема аппроксимации многозначных КА. Розглянуто новий клас математичних моделей для теорії обчислень — клітинні автомати (КA) з розгалуженими комплекснозначними перехідними функціями. Ключовим моментом є можлива багатозначність станів клітини з такими перехідними функціями. Розглянуто різні випадки з перехідними функціями з комплексними значеннями. Описано динаміку КA на одній гілці та на різних ізольованих гілках. Запропоновано розгляд випадку переходів станів між гілками, а також випадку неперервнозначних КA та їх кінцевозначних наближень. Поставлено проблему апроксимації багатозначних КА. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020-12-29 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/228540 10.20535/SRIT.2308-8893.2020.4.11 System research and information technologies; No. 4 (2020); 141-147 Системные исследования и информационные технологии; № 4 (2020); 141-147 Системні дослідження та інформаційні технології; № 4 (2020); 141-147 2308-8893 1681-6048 en https://journal.iasa.kpi.ua/article/view/228540/227587 |
| spellingShingle | клітинні автомати комплекснозначні перехідні функції поверхні Рімана неперервнозначні КА розгалуження наближення багатозначності обчислення Makarenko, Alexander Моделі клітинних автоматів з комплекснозначними функціями переходу |
| title | Моделі клітинних автоматів з комплекснозначними функціями переходу |
| title_alt | Cellular automata models with complex valued transition functions Модели клеточных автоматов с комплекснозначными функциями перехода |
| title_full | Моделі клітинних автоматів з комплекснозначними функціями переходу |
| title_fullStr | Моделі клітинних автоматів з комплекснозначними функціями переходу |
| title_full_unstemmed | Моделі клітинних автоматів з комплекснозначними функціями переходу |
| title_short | Моделі клітинних автоматів з комплекснозначними функціями переходу |
| title_sort | моделі клітинних автоматів з комплекснозначними функціями переходу |
| topic | клітинні автомати комплекснозначні перехідні функції поверхні Рімана неперервнозначні КА розгалуження наближення багатозначності обчислення |
| topic_facet | клітинні автомати комплекснозначні перехідні функції поверхні Рімана неперервнозначні КА розгалуження наближення багатозначності обчислення cellular automata complex-valued transition functions Riemann surfaces continuous-valued CA branching approximation of multivaluedness computations клеточные автоматы комплекснозначные переходные функции римановы поверхности непрерывнозначные КА ветвление аппроксимация многозначности вычисления |
| url | https://journal.iasa.kpi.ua/article/view/228540 |
| work_keys_str_mv | AT makarenkoalexander cellularautomatamodelswithcomplexvaluedtransitionfunctions AT makarenkoalexander modelikletočnyhavtomatovskompleksnoznačnymifunkciâmiperehoda AT makarenkoalexander modelíklítinnihavtomatívzkompleksnoznačnimifunkcíâmiperehodu |