Cellular automaton
Cellular or cellular automata modeling are spatially discrete dynamic systems, the development of individual cells at the time t 1 depends primarily on cell states in a given neighborhood, and the own state at the time t.
Description
A cellular automaton is defined by the following variables:
- A space R ( Zellularraum )
- A finite neighborhood N
- A set of states Q
- A local transition function.
The Zellularraum has a certain dimensionality, it is usually 1 - or 2- dimensional, but it may well be höherdimensional. It describes the appearance of a cellular automata by a global configuration, which is a mapping from the Zellularraum in the set of states, that is, one assigns to each cell of the automaton to a state. The transition of a cell from one state ( local configuration ) in the next is defined by state transition rules that can be deterministic or stochastic. The state transitions are made for all the cells according to the same transfer function and the same time. The cell states may be discrete as the time steps. In general, the number of possible states is small: only a few state values range for the simulation of the most complex systems.
A distinction (also called neighborhood index) two different neighborhoods:
History of Cellular Automata
Cellular automata were introduced around 1940 by Stanislaw Ulam at Los Alamos. John von Neumann, a former colleague Ulam, took up the idea and expanded it to a universal computation model. He presented a cellular automaton with 29 states that could reproduce a given pattern over and over again yourself. He was describing the first to cellular automata, which is computing and construction universal.
Up to the 1960s, analog computers were superior to digital computers for some questions. An analog cellular automaton for the simulation of groundwater flow is described in the article analog computer in more detail.
In the 1970s, John Horton Conway's Game of Life became famous.
1969 Konrad Zuse published his book " Rechnender space ", in which he assumes that the laws of nature discrete rules to follow and the whole incident was the result of the work of a giant cellular automaton in the universe.
1983 Stephen Wolfram published a series of fundamental papers on cellular automata and 2002, the book A new kind of science.
Tungsten -dimensional universe
Stephen Wolfram's cellular automaton is a particularly beautiful and simple model universe. It consists of a single space and a time dimension. The picture shows the space dimension is drawn horizontally and the time dimension is perpendicular to the bottom. ( The image contains three different compositions. ) The space dimension is finite, but unbounded, because her right and left end are topologically linked.
The space-time elements of this universe can only be empty or full. The " Big Bang " ( in the top picture lines ) this space-time elements are filled with 50 percent probability. There is only one law of nature, which is a proximity effect. The short range comprises the two left-hand neighbor of a space-time element, the space-time element itself, and the right two neighbors of the space-time element. If two or four space-time elements at close range are full, then in the next time interval of this space-time element is also full, otherwise it is in the next time interval empty. There are no other rules.
Although there is no action at a distance and no supervisory unlike computer games, this model universe developed into startling complexity. After the Big Bang, an elimination phase takes place, as in the real universe too. After that arise short-lived but ordered structures that go out sometime. However, some of the ordered structures are long -term stable, oscillate some of them, others of which are dimensionally stable in time. Both the oscillatory and of the dimensionally stable structures exist in both stationary and movable types. The maximum exchange rate of the universe may be only two space units per time unit. If collisions occur between the stable moving objects, then sets again Chaos, and a further elimination phase takes place.
One simplified even further and takes into account the state of the element itself only each the right and left neighboring element, there are exactly 8 control elements. An example is below. In total there are 256 such rules. Even under these more simple rules show some amazing complexity. The most interesting is the "Rule 110 ":
Rule 110
See also: Rule 30
Classification
Stephen Wolfram defined in A New Kind of Science, and in quite a few designs from the mid -1980s, four classes into which one the cellular automata ( more precisely, the rules which they execute ) can be subdivided according to their behavior. Earlier authors attempted only to identify the type of pattern for certain provisions.
The expense after ordered were the classes:
- Class 1: Almost all original patterns evolve quickly into a stable and homogeneous state. Thus, each randomness disappears in the first patterns.
- Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some contingencies of the first pattern can filter out one, but some may remain. Local changes to the initial pattern tend to remain local.
- Class 3: Nearly all initial patterns evolve pseudo-random or chaotic. Each stable structure can be quickly destroyed by noise. Local changes to the initial pattern tend to spread to infinity.
- Class 4: Nearly all initial patterns evolve into structures that interact with complex and interesting. Finally informative origin pattern, as in Class 2 standard, stable or oscillating structures arise, but the number of steps required to reach this state can be very large even for simple patterns. Local changes to the initial pattern can spread to infinity.
Tungsten has suggested that not all cellular automata class 4 to be able to perform universal computations. The universality has been confirmed especially for the Rule 110 and Conway's game of life.
Program cellular automata
This short script written in the Python programming language, can simulate and produces as output a picture in graphic format Portable Graymap (. Pgm ) all 256 one-dimensional cellular automata. When calling the desired rule number must be entered 0 to 255.
Import sys this file if len ( sys.argv ) = 2 or int ( sys.argv ) not in range ( 0,255 ): sys.exit () w = 999 r = s = w * r [w / 2 ] = 1 Z = "" d = 0 for j in range ( 0, w / 2): n = (r << 1 ) r o = "" for i in range (1, w): o = " 0 " if r [i ] == 1 else "15" z = z o "\ n" for i in range (2, w): n = (n << 1 ) r [i ] if n> = 8: n = 8 s [i -1] = ( int ( sys.argv ) >> n ) % 2 r = s D = 1 print " P2" print str ( w -1 ) " " str ( d) print " 15" print z Examples of cellular automata
- Conway's Game of Life ( Game of Life ) is a simple two-dimensional cellular automaton that generates amazing structures.
- Langton loops simulate capable of self-replication organisms in a cellular automaton.
- Pascal's triangle can also be interpreted as a simple cellular automaton.
- The Nagel-Schreckenberg model is a cellular automaton for the simulation of road traffic especially on highways.
- FHP the model is used for simulation of gases and liquids.
- A very simple cellular automaton is the ASEP.