What is a binary cellular automaton

Cellular automata as simple self-organizing systems

Transcript

1 Cellular automata as simple self-organizing systems René Schlossus Sebastian Walther December 2006 Abstract This article gives an overview of the theory of cellular automata, the reasons for their introduction and their most important representatives. Stephen Wolfram's works from 1982 to 1988, in which he dealt with the mathematical side of cellular automata, are in the foreground of more detailed considerations. Based on this, the structure, functionality and basic properties of cellular automata are described and presented in the form of practical application examples from research and technology. 1

2 Contents 1 History 3 2 Fundamentals Definition according to John von Neumann Formal description Wolfram model Rules States Simple initial states Random initial states Practical application examples Conclusion 11 2

3 1 History In 1940 Stanislaw Marcin Ulam (April 13, 1909 in Lwów (Lemberg), Poland; May 13, 1984 in Santa Fe, USA) presented the cellular automatons as part of the Manhattan project in Los Alamos. His goal was to create a model of thought with which it is possible to describe complex systems. This gave him an approach to programming analog computers that were supposed to simulate such complex systems. With the idea of ​​cellular automata, Ulam only provided a theoretical entry point. John von Neumann (December 28, 1903 in Budapest Austria-Hungary; February 8, 1957 in Washington DC, USA), who was a friend and colleague of Ulam, took up this approach and developed it into a universal calculation model. From this he then developed a cellular automaton that showed 29 states and was able to reproduce a given pattern over and over again. It was a reversible type of cellular automaton, but it showed how a cellular automaton develops through self-reproduction. In the late 1960s, Aristid Lindenmayer (November 17, 1925 in Budapest; October 30, 1989) combined cellular automata and other methods to model plant growth. The resulting L-System is still used today in a wide variety of forms. Konrad Zuse (June 22, 1910 in Berlin; December 18, 1995 in Hünfeld near Fulda) published his book Calculating Room in 1969, assuming that the laws of nature follow discrete rules and that the entire universe is the result of a gigantic cellular automaton. Wikipedia () In 1970 the English mathematician John Horton Conway (December 26, 1937 in Liverpool) became famous for the game Game of Life. The system consists of two-dimensionally arranged cellular automata, and Stephen Wolfram (August 29, 1959 in London, England, Great Britain), inventor of Mathematica, published a series of fundamental articles on cellular automata in which he believed that cellular automata could revolutionize science. 3rd

4 2 Basics 2.1 Definition according to John von Neumann A cellular automaton is a system of cells which interact with each other. The system shows a complex behavior with the following characteristics (Artur P. Schmidt,): 1. The system consists of 1-, 2- or 3-dimensional networks of cells. 2. Each cell can assume one of n possible discrete states. 3. The system follows a specific time dynamic in which the cells take into account the states of the respective neighboring cells when transitioning to new states. 2.2 Formal description A cellular automaton can be formally described as follows (Wikipedia,): a space R (cell space) a finite neighborhood N state set Q a local transfer function: δ: Q N Q It is not graphically represented by e.g. is represented by a graph, but by a grid of cells (cell space) that can assume certain states from the set of states Q. This is necessary because a cellular automaton is a non-sequential automaton, i.e. all changes of state of a clock are carried out in all places (cells) at the same time. In addition, the new state of a cell depends not only on its own current state, but also on the current states of the cells in its neighborhood N. In 2-dimensional space or in a square grid, a distinction is made between the Von Neumann neighborhood (Fig. 1), in which only the areas that have an edge in common with the base area are considered neighbors. And the Moore neighborhood (Fig. 2), in which all areas that have at least one corner in common with the base area are considered neighbors. 4th

5 Figure 1: Von Neumann neighborhood Figure 2: Moore neighborhood Due to varying neighborhood relationships, the actual state transitions cannot be represented graphically, i.e. only the current state of the machine is shown. At the beginning, the cellular automaton is described by a global configuration, which is a mapping from the cell space R into the state set Q, that is, one assigns a state to each cell of the automaton. Then a local transfer function or a state transfer rule is defined, which transfers the cell from one local configuration to the next, whereby this can be done deterministically or stochastically. The number of possible states is usually very small (e.g. 1 and 0), but this is sufficient for the simulation of highly complex systems. 3 Wolfram 3.1 Model Stephen Wolfram dealt with elementary cellular automata, which consist of only one space and one time dimension (Fig. 3). Similar to a clock, the spatial dimension has a beginning and an end, but these are interconnected. The time and space dimensions create a grid consisting of pages that can be either empty (0) or full (1). With the first clock pulse (Big Bang), the pages are filled with a 50 percent probability. The values ​​of each side of the next time cycle result from well-defined rules (natural law). These include the values ​​of a left neighbor, a right neighbor and the page itself. This means that the automaton becomes very complex. This creates short-lived, but ordered patterns that either disappear again or are long-term stable. The long-term stable patterns can either be dimensionally stable or oscillating. Both dimensionally stable and oscillating patterns appear stationary or movable. If stable moving objects collide, chaos sets in and the patterns are erased. 5

6 Cellular automata can also be viewed as parallel computers, whereby the initial configuration describes the program and the input data, and the development over time generates the output. According to Church's thesis in the formal theory of computability, such cellular automata can potentially simulate all possible systems. (Stephen Wolfram, 1982, Introduction) Figure 3: Wolfram's 1-dimensional universe 3.2 Rules In an elementary cellular automaton, the possible rules for a state transition are limited to (256 = 2 (23)). Since, apart from the state of the cell itself, only the states of the first left and right neighbors are decisive for the subsequent state. These rules can be interpreted as a Boolean operation on the values ​​of the 3 neighboring cells. The names of the rules are given as a decimal equivalent to their binary notation (e.g. rule no.90 =). Fig. 4 shows the set of state transitions for an elementary cellular automaton using rule 90 as an example. Each of the eight possible sets of values ​​for a side and its nearest neighbors appears in the top line. In the lower line, on the other hand, the subsequent states of the current cell are recorded, which together represent the binary representation of the rule. Of the 256 rules, only the 32 rules of the form α 1 α 2 α 3 α 4 α 2 α 5 α 4 0 are legal, i.e. they fulfill the symmetry and leave the idle configuration

7 Figure 4: State transitions of rule 90 for an elementary cellular automaton ration unchanged. (Stephen Wolfram, 1982, Introduction) 3.3 States Wolfram specifies 4 classes of target states of an elementary cellular automaton (shown here on a 1-dim automaton and based on a single full cell, with empty spaces appearing black and solid white): Class 1 more homogeneous State of equilibrium (Fig. 5) (Stephen Wolfram, 1984, 5th Class 1 Cellular Automata) Figure 5: Class 1 (rule 4 =) Class 2 constant or periodic final state (Fig. 6) (Stephen Wolfram, 1984, 6th Class 2 Cellular Automata) Figure 6: Class 2 (rule 50 =) 7

8 Class 3 chaotic final state of fractal dimension (Fig. 7) (Stephen Wolfram, 1984, 7. Class 3 Cellular Automata) Fig. 7: Class 3 (rule 18 =) Class 4 complex patterns as attractor (Fig. 8) (Stephen Wolfram, 1984, 8. Class 4 Cellular Automata) Figure 8: Class 4 (rule 86 =) Simple initial states In simple initial states, which are also called ordered initial states, selected cells are explicitly set to 1 or filled in time cycle 1 (grid line 1). In the simplest case this is just a single cell. A mathematical example of a simple initial state with only one filled cell and the resulting pattern is the Pascal triangle modulo 2. It belongs to class 3 with the final state of fractal dimension (see Fig. 9, lower figures). As you can see from this, a full cell and a rule from class 3 are sufficient to represent this complex mathematical issue in a very simple way. (Stephen Wolfram, 1982, Simple Initial States) 8

9 Figure 9: Algebraic and geometric representation of Pascal's triangle Random initial states Random initial states are disordered initial states in which each side is assigned the value 1 independently and randomly with the probability p 0, so that an initial density p = p 0 of 1 values ​​or full cells result. Wolfram also imagined the creation of the universe in this way. At the beginning there is chaos, which over time leads to development in a certain direction (pattern) through natural laws (rules) and a certain togetherness (neighborhood). However, conflicts between different paths can lead to chaos, which can also lead to the complete annihilation of the developments. (Stephen Wolfram, 1982, Random Initial States) Figure 10: Development of the density over time from full pages based on a random initial state of density 0.2 9

10 3.4 Practical application examples Practical application examples for cellular automata and their relationship are: Pattern generation Algorithmic composition of music Basis: Simulation 1. Cellular automaton based on Wolfram's model. 2. Each epoch of the automaton corresponds to a beat of the music. 3. In the simplest case, exactly one tone is assigned to each cell position. However, this doesn't sound very nice. By using different rules and adjustments, e.g. on MIDI tones, the sound can be improved. Details on the adaptation and implementation in Java can be found on the website of Paul Reiners (, Cellular automata and music), a software developer at IBM. Traffic simulation according to the Nagel-Schreckenberg model (Prof. Dr. Michael Schreckenberg,) The street is divided into 7.5m long sections (cells). This is typically the space a vehicle takes up in a traffic jam. Each cell is either empty or occupied by a vehicle with a discrete speed v from 0 to MAXSPEED (e.g. MAX-SPEED = 5 cells / time step). The number of free cells between two consecutive vehicles is called the gap. The deceleration probability P is the stochastic element (noise) in this model, when P = 0 one speaks of the deterministic model. Now for the update rules: 1. Accelerate: If the gap is greater than your own current speed v, then increase the speed by 1, but at most to MAXSPEED. 2. Braking to prevent rear-end collisions: If the gap is smaller than your own current speed v, then brake. 10

11 3. Slowing down: With the probability P, the speed v of a vehicle is reduced by 1. 4. Driving: Each vehicle moves forward by v cells. Cryptography 4 Conclusion bit stream encryption Procedure: 1. Determine the number of cells of the 1-dim cellular machine to be used, corresponds to the key length in bits. 2. Initialization of the machine, i.e. allocation of the cells with 1 or 0, either randomly, in which case you have to remember all states, or you do it according to a certain pattern. E.g. you could think of a password and add its binary representation to the key length one after the other. 3. Selection of a rule that changes the initial state in any case (e.g. rule 86). 4. Determination of the number of evolution steps to be carried out by the machine. 5. Construction and execution of the machine with the parameters mentioned. 6. If necessary, appending the values ​​of the last generation of the machine up to the length of the text to be encrypted / decrypted. 7. XOR operation of the (cipher) text with the generated bit stream. Cellular automata have a wide range of applications because they are universal in terms of calculation and design. However, they rarely occur in their pure form, but are combined or modified with other processes. Stephen Wolfram only considers one-dimensional elementary cellular automata as a simplification, which, however, can already be highly complex. All in all, Wolfram's work is very mathematically oriented and an 11 is required for a detailed consideration

12 larger frames. However, his published articles are only an overview of the application of cellular automata in a particular context. That is why this elaboration is limited to an overview of the historical development and the basics of cellular automata, without going into more detail, e.g. on complicated mathematical properties. It should also be mentioned that Wolfram's work was more than 20 years old at the time this document was written, and that although cellular automata are still the subject of research (ACRI, 2006), the field is very diverse. It is also difficult to get up-to-date information on this. 12

13 Literature ACRI. Cellular Automata for Research and Industry Artur P. Schmidt. Paul Reiner's cellular automata. Cellular automata and music Prof. Dr. Michael Schreckenberg. Traffic flow modeling. essen.de/servlets/derivateservlet/derivate- 190 / nagel% 5Fschreckenberg% 5Fmodell% 5F1.htm, Stephen Wolfram. Cellular Automata as Simple Self-Organizing Systems. cellular / index.html, Stephen Wolfram. Universality and Complexity in Cellular Automata. universality / index.html, Wikipedia. Cellular automaton