The idea of cellular automata appeared in the late forties of the 20th century. She is
was conceived and formulated by John von Neumann and Conrad Zus
independently as a universal computing environment for building,
analysis and comparison of the characteristics of the algorithms.
The book [1] provides the following definition of cellular automata.
"Cellular automata are discrete dynamical systems, the behavior
which is completely defined in terms of local dependencies. AT
to a large extent also the case for a large class of continuous
dynamical systems defined by partial differential equations. In that
cellular automata in computer science are analogous to the physical concept
"Fields" ... a cellular automaton can be thought of as a stylized world. Space
represented by a uniform grid, each cell or cell of which contains
several data bits; time goes forward in discrete steps and the laws of the world
expressed by a single set of rules, let's say a small reference
a table by which every cell at each step calculates its new state
on the states of her close neighbors. Thus, the laws of the system are
local and the same everywhere. “Local” means that in order to
see what happens here a moment later, just look at the state
Neighborhood environment: no long range is allowed. "The Same"
means that the laws are the same everywhere: I can distinguish one place from another
only by the shape of the landscape, and not by some difference in the laws. ”
It should be noted that cellular automata are not just machines
working with a field divided into cells. Area of use of cellular automata
almost limitless: from the simplest "tic-tac-toe" to artificial
intelligence. The topic of cellular automata is very relevant, as it can lead to
clues to many questions in the surrounding world. The creator of the game "Life" Conway,
believed that our universe can be represented by a cellular automaton, which
controls the movement of elementary particles in accordance with certain rules
(By the way, Conway has now come up with another use of cellular automata in this
area: imagine a fairly large number of "primary broth" from
randomly distributed cells if one can expect the appearance of such chaos
structures capable of self-reproducing themselves, this is another confirmation
theory of the origin of life on Earth).
Cellular automata are used to simulate hydrodynamic and
gas-dynamic flows [2, 3]. The hydrodynamic equations correspond to
a mathematical model describing the behavior of a lattice gas, one of
cellular automata, at the macro level. Structures arising in these cellular
automatic, similar to the disturbance of the surface behavior of fluid flow
mechanical obstacle. Primitive one-dimensional cellular automata can
to simulate the combustion process of a different nature. Currently theory
cellular automata most promisingly attached to the question of the development
self-repairing electronic circuits [4].
Cellular automata are applicable not only in mathematics and physics, but also in
biology [5], economics, sociology, computer science, etc. Using cellular
automata successfully solved the problems of modeling currents with a free
four
the boundary [6], the propagation of heat fluxes [7], the growth and dynamics of domains [8],
the growth of dendrites [9], descriptions of the movement of the crowd [10]. They can be used with
compilation of genetic algorithms. Imagine a cellular automaton for
cells whose additional condition for survival is to produce
some sequence of output data (let's call it conditionally reaction) in
response to a sequence of input data (irritation, which is a property
environment), predicting the subsequent state of the environment. To such a machine
functioned, a random rule change mechanism is also added
generating a reaction (mutation) and transferring to the newly emerging cells information about
Neighborhood Response Rules (Inheritance). In addition to the study of conditions
development of models of living systems, this approach allows us to solve some
practical tasks, in particular, finding the shortest path on a graph. Graph structure
encoded in some way in the chromosomes of cells. It is assumed that
algorithms acquired due to mutations and inheritance will be
match the solution of the problem.
According to their behavior, cellular automata are divided into four classes. TO
first class includes machines that come after a certain time to
steady homogeneous state. Second class machines after some
time after start-up generate stationary or periodic in time
structures. In the third-class machines, after some time ceases
there is a correlation of the process with the initial conditions. Finally, the behavior
fourth-class automata are strongly determined by the initial conditions and with their
using, you can generate very different patterns of behavior. Such
automata are candidates for a prototype cellular computing machine. AT
particular, using the specific cellular configurations of the game “Life”,
which is just a machine of the fourth type, you can build all
discrete elements of a digital computer.
We note another application of cellular automata in computer science -
encryption and data compression.
Cellular automata are applicable when implementing an effective system.
pattern recognition. One of the possible ways to create it is to build
dynamical system whose attractors in its configuration space
would be typical picture-images. Initial conditions will always be in the area.
the attraction of one of the pictures, over time the system transforms the initial
parameters, bringing them to the closest structure - the attractor. I.e
the image will be automatically recognized. And you can create
learning recognition systems, in them the laws of evolution have a state
programming. You can also use cellular automata when solving
optimization tasks. Often, tasks arise in different areas of activity.
finding the best option from an unlimited number of possible. Accurate
solutions are usually not required, but a discrete computer is not even capable
approximately give the best result.
Thus, cellular automata have found and are widely used in
many areas of human activity, many of whose tasks have become possible
solve only with a computer. Consider a few examples of cellular
automatons.
Content Six points of view on cellular automata (CRAs) Creators of modern theory and practice of the CRA Approach to visualization and auditing of AC spacecraft in designing and implementing software and hardware systems for spacecraft in designing and implementing software and hardware systems Quantum cellular automata to thinking 2 Lexical clarification: when translating into English - (cellular) automata in pl. number, and in the only - automaton (following the rules of Latin)
3 I. Six points of view on cellular automata. Thesis. A KA comment is just nothing more than a mathematical toy like a children's kaleidoscope and an exercise for young programmers. To understand what KA is, you just need to play the Game of Life a little. A finite automaton is a fundamental abstraction for sequential computing, a spacecraft for parallel Classic spacecraft operates synchronously, but asynchronous spacecraft are also possible. J. Von Neumann. KA is only a certain numerical method for discretization of model diff. Eq. continuous valued cellular automata, KA Oono-Kohomoto for the diffusion of KA is a special language of the mat. models describing spatially distributed systems How, then, to find local rules so that the system has the desired dynamics? KA is a branch of mathematics, where Stephen Wolfram's computational experiment is very significant, “A New Type of Science” The whole Universe is a giant KA, there is a “calculating space” Edward Fredkin, direction digital philosophy 3
4 The sixth point of view (continued): QA - “a discrete view of the world” For the mathematics of the 21st century, the spacecraft apparatus has the same fundamental significance as differential equations in the XVIII – XX centuries. The value of the spacecraft is comparable to Einstein’s theory of relativity in physics, and Darwin’s theory of natural selection in biology. The fundamental nature of spacecraft is confirmed by the expanding range of applications from quantum chromodynamics to crowd behavior. To define a classic spacecraft, you need to determine: Cell state (bit) Field dimension and spacecraft grid (square) Neighborhood pattern (Mura - 8 cells plus one) Local transition rules (transition conditions) for the boundary cells (no boundaries) Initial state KA fields Mode of operation (synchronous, not block) Degree of structure homogeneity These seven conditions create a variety of KA, not counting the semantic load 4
Comments
To leave a comment
System modeling
Terms: System modeling