I have previously wrote about various classic 2D cellular automata: WATOR, the voting game and Wireworld (here and here). There is a whole class of simpler one dimensional automatons though. These were researched by Stephen Wolfram (of Mathematica and WolframAlpha fame).
What is the elementary cellular automaton anyway?
Imagine a boundless tape of cells (not necessarily infinite; it could connect end to end like a loop). The cells can be in '1' or '0' state at any given moment. The time passes in turns in this universe, and each turn the cell changes its value depending on the state of its neighbours and itself. For example, consider a fragment of the tape stating '...010...'. For this combination of states, a rule might say that the value of the center cell in this fragment becomes '0' the next turn.
There is a limited number of such rules. Since only three bits govern the evolution of the center cell state, the combinations are '000', '001', '010' etc. (8 combinations) - and for each of these the center state can become either '0' or '1', the total number of rules is 2^8 = 256 rules. These are easily encoded as a number. For instance, rule 11010 = 011011102 says that the center cell becomes '1' when the tape fragment the turn before is wither '110', '101', '011', '010', '001' (see the picture below).
 |
| Fig. 1. Rule 110. |
I made a simple demo for testing various elementary cellular automaton rules. The demo is available HERE, and its source code is hosted on Gitlab HERE. The demo lets you easily change the rules (even as the automaton is working) either by typing the number in or clicking on the graphical tape fragment representations on the left side. You can also modify the tape cells manually by clicking and moving a mouse in the view in the middle. The left mouse button sets the tape cells to '1' and the right mouse button clears them to '0'. You can also randomize the state of the tape the automaton starts from.
 |
| Fig. 2. Elementary Cellular Automata demo. |
It's a simple world, but it can still yield interesting results. Some of them are presented below.
Rule 90
Starting from a single pixel in the middle we get a Sierpinski triangle of sorts:
 |
| Fig. 3. Rule 90 makes a Sierpinski triangle. |
Rule 60
Rule 60 also makes a Sierpinski triangle but sort of kicked to its side:
 |
| Fig. 4. Rule 60. |
Rule 30
It's an interesting one. Seemingly random structures emerge under this rule. It is reportedly used for some of the randomization routines in Wolfram's Mathematica.
 |
| Fig. 5. Rule 30. |
Rule 110
This one produces curious structures that move across the tape and interact between themselves. It has been proven that rule 110 is Turing complete and thus can be used to model any calculation. I have no idea how to use it yet!
 |
| Fig. 6. Rule 110 is a Turing complete CA. |
It could certainly be interesting to experiment with the remaining rules and see what they are capable of. Perhaps you have an idea of how this simple setup could be extended? Feel free to play around with the provided demo.
More reading:
No comments:
Post a Comment