Cellular automat

from Wikipedia, the free encyclopedia
Example of a spatiotemporal pattern that develops in a cellular automaton

Cellular or cellular automata are used to model spatially discrete dynamic systems , whereby the development of individual cells at the point in time depends primarily on the cell states in a given neighborhood and on one's own state at the point in time .

description

A cellular machine is defined by the following parameters:

  • a room ( cellular room )
  • a finite neighborhood
  • a set of states
  • a local transfer function .

The cellular space has a certain dimensionality , it is usually one or two-dimensional, but can also be higher-dimensional. The appearance of a cellular automaton is described by a global configuration , which is a mapping from the cellular space into the state set, that is, a state is assigned to each cell of the automaton. The transition of a cell from one state ( local configuration ) to the next is defined by state transition rules, which can be deterministic or stochastic. The state transitions take place for all cells according to the same transfer function and simultaneously. The cell states can be discrete like the time steps. As a rule, the number of possible states is small: only a few state values ​​are sufficient to simulate even highly complex systems.

There are two different neighborhoods (also called neighborhood index):

History of cellular automata

Cellular automata were introduced by Stanislaw Ulam in Los Alamos around 1940 . John von Neumann , a colleague of Ulam at the time, took up the idea and expanded it into a universal calculation model. He presented a cellular automaton with 29 states that could reproduce a given pattern again and again. He was the first to describe a cellular automaton that is universal in terms of calculation and design. According to von Neumann, it is suitable for problems of biological organization, self-reproduction and the evolution of complexity. The cellular automat is thus also an important basis for artificial life .

Up to the 1960s, which were analog computers to digital computers superior to some questions. An analog cellular automaton for simulation of groundwater flow is described in the article analog computer accurately.

In the 1970s, John Horton Conway's Game of Life became famous.

In 1969 Konrad Zuse published his book “Computing Space”, in which he assumes that the laws of nature follow discrete rules and that everything that happens in the universe is the result of the work of a gigantic cellular automaton.

In 1983 Stephen Wolfram published a series of foundational papers on cellular automata and in 2002 the book A New Kind of Science .

Wolfram's one-dimensional universe

Wolfram's one-dimensional universe

Computer scientist Stephen Wolframs cellular automaton is a particularly beautiful and simple model universe . It consists of only one space and one time dimension. In the picture the space dimension is drawn horizontally and the time dimension runs vertically downwards. (The picture contains three different sections of the picture.) The spatial dimension is finite, but unlimited, because its right and left ends are topologically connected.

The space-time elements of this universe can only be empty or full. In the case of the “ Big Bang ” (in the uppermost picture lines) these space-time elements are filled with a 50 percent probability. There is only one law of nature that represents a close-up effect. The near area comprises the left two neighbors 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 are full in the vicinity, then this space-time element is also full in the next time interval, otherwise it is empty in the next time interval. There are no other rules.

Although, in contrast to computer games, there is no action at a distance and no control authority whatsoever, this model universe is developing into astonishing complexity. After the Big Bang, there is an elimination phase, just like in the real universe. After that, short-lived but orderly structures emerge, which at some point disappear. However, some of the ordered structures are long-term stable, some of them oscillate, others are dimensionally stable over time. Both the oscillating and the dimensionally stable structures exist in both stationary and movable types. The maximum exchange speed of this universe can only be two units of space per unit of time. When collisions occur between the stable moving objects, chaos sets in again and another phase of elimination takes place.

If one simplifies even further and only takes into account the state of the element itself, only the right and left neighboring elements, there are exactly 8 rule elements. An example is given below. There are a total of 256 such rules. Even among these even simpler rules, some show astonishing complexity. One of the most interesting is the "rule 110":

Rule 110

new state of the middle cell 0 1 1 0 1 1 1 0
current state of three neighboring cells 111 110 101 100 011 010 001 000
The first 200 development steps (from bottom to top) of rule 110, when only one cell is full and all others are empty at the beginning .
The first 3200 development steps of rule 110. Only the left side is shown.

See also: rule 30

Classification

In A New Kind of Science and in a number of papers from the mid-1980s, Stephen Wolfram defines four classes into which cellular automata (more precisely: the rules they work through) can be divided according to their behavior. Previous authors simply tried to identify the type of pattern for certain regulations.

According to the effort, these were the classes:

  • Class 1: Almost all original patterns quickly develop into a stable and homogeneous state. As a result, any randomness in the first patterns disappears.
  • Class 2: Almost all original patterns develop quickly into stable or oscillating structures. Some coincidences of the first patterns can be filtered out, but some can remain behind. Local changes to the original pattern tend to remain local.
  • Class 3: Almost all of the original patterns develop in a pseudo-random or chaotic manner. Any stable structure can be quickly destroyed by noise. Local changes to the original pattern tend to spread to infinity.
  • Class 4: Almost all original patterns develop into structures that interact in a complex and interesting manner. Finally, informative original patterns can, as is usual in class 2, result in stable or oscillating structures, but the number of steps required to achieve this state can be very large, even for simple patterns. Local changes to the original pattern can spread indefinitely.

Wolfram suggested that not all class 4 cellular automata are capable of performing universal computations. The universality has been confirmed especially for Rule 110 and Conway's Game of Life .

Programming cellular automata

This short script, written in the programming language Python , can simulate all 256 one-dimensional cellular automata and generates an image in the graphic format Portable Graymap (.pgm) as output . When calling up, the desired rule number, 0 to 255, must be entered. 

 1 from optparse import OptionParser
 2 
 3 if __name__=="__main__":
 4     parser = OptionParser()
 5     parser.add_option("-r", dest="rule", help="Rule number 0..255.")
 6     parser.add_option("-f", dest="file_path", help="File path")
 7 
 8     (option, args) = parser.parse_args()
 9     rule = option.rule
10     file_path = option.file_path
11 
12     w = 1000
13     r = s = [0] * w
14     r[int(w/2)] = 1
15     z = []
16     d = 0
17 
18     for j in range(0, int(w/2)):
19         n = (r[0] << 1) + r[1]
20         o = ""
21         for i in range(1, w):
22             o += " 0 " if r[i]==1 else "15 "
23         z.append(o + "\n")
24         for i in range(2,w):
25             n = (n << 1) + r[i]
26             if n >= 8: n-=8
27             s[i-1] = (int(rule) >> n)%2
28         r = s
29         d += 1
30 
31     f = open(file_path,'w')
32     f.write("P2\n")
33     f.write(str(w-1) + " " + str(d) + "\n")
34     f.write("15\n")
35     for i in range(len(z)-1, 0, -1):
36         f.write(z[i])
37     f.close()

Examples of cellular automata

See also

literature

Web links

Commons : Cellular automata  - collection of images, videos and audio files

Secondary literature

Visualizations and implementations

Individual evidence

  1. ^ Daniel Dennett, (1995), Darwin's Dangerous Idea, Penguin Books, London, ISBN 978-0-14-016734-4 , ISBN 0-14-016734-X
  2. ↑ NetLogo Models Library: CA 1D Elementary Cellular Automata. Accessed November 26, 2018 .