Cellular automata: The Atoms of Complexity
When we face with the complexities in the world one way to understand them is to decompose it to its constitutes. For example, when we don’t understand the human body we try to break it down to its parts like the liver, the heart, and the brain and if we still don’t understand the mechanisms we go further until we get to the living cells. We do all the time in science. In the biggest and most general case we follow this approach on the whole physical reality scale. we broke down the matter to get to the atoms, electrons, and quarks. It’s no wonder why we still do it because it was a successful way of looking at the world. The scientific approach for centuries was based on the idea of reductionism. This thesis wasn’t always easy to apply. One great example is the effort of scientists to understand the sub-atomic world. The results were the opposite: not only we couldn’t simplify things but we discovered the weird, impossible-to-understand world of quantum mechanics. QM defies all common sense explanations and definitions in the world of science.
Complexity, but has a long history just like science. Newton was the first scholar who realized that his elegant theory lives on a shaky edge. The 3-body problem showed that predicting the future of a physical system even in its most basic forms is a daunting problem.
But, besides having all these difficulties in understanding physical theory which still needs to be learned, mathematicians and physicists started to discover even more problems with our formal systems for understanding the world. They started to create artificial systems that exhibit unsettling complexities. Most of these systems were so easy to program and simulate in a basic computer. John Conway and Stephen Wolfram were the pioneers of creating these systems.
Stephan Wolfram started to understand the knots and bolts of neural networks in the ’80s but he was looking for even simpler models. So he decided to create cellular automata. Cellular automata are very much like board games. You have a 1d array of cells. Each cell can be filled(1's) or empty(0's). For example, you can imagine a possible configuration like below:
Now, we want to move the 1’s. We need some rules! Assume that the next state of each cell will be determined with the configurations of two surrendering cells. In a more formal way, the next state of the cell is a function of the left and right cells to it.
this means that the current state(t) will be determined by the previous state(t-1). In the terminology of cellular automata, we evolve from one generation to the next generation.
If this is the case, we have to decide about 8 possible configurations(2³ from 000 to 111). For example, one imaginable rule can be like this:
This rule implies that if your desired cell is currently 1 and two adjacent cells are also 1, the next state for your desired cell would be 0. Or, if your cell is 1 and the right cell to it is 0 and the left cell is 1 in the next generation the cell will hold 1. So it is sufficient to just slide a 3 cell window over the array(from right to left or the other way) and reference to our rule set and choose what will be the next state. For example, below the window is on 010 and with consulting from the rule set we realize that the next generation of the cell will be 0!
What you see above is an arbitrary rule. we can change the rules the way we wish. As another example, you can check out the rule of the gif below.
So, the question is: how many different rules we can have? Again all the possible combinations of 0’s a 1’s for the eight windows(2⁸=256). So, we can have 256 possible rules. we can name the rules after their number hence we can have rule 0 to rule 255. For example, the first example above had the number 90 = 01011010. Wolfram started to study the behavior of these simple systems. To this end, he sorts the rules and tried to see their evolution through time one by one. To see everything visually he used filled and empty cells for 1’s and 0’s respectively. For example, rule 90 would be like below:
Then he used the below configuration as the first generation for all the cases.
He applied the rules and stacked the result of each generation right below the previous one. As you might expect most rules had a very simple dynamic. For example, rule 0 will tell you to substitute everything with zero, so, nothing after the first generation. But some rules had repetitive patterns like rule 6 that you can see below:
Some rules go even further to surprise you with amazing fractal patterns like rule 90:
This pattern is interesting and shows some forms of complexity but it is still too simple to be considered as the candidate for “true” complexity.
But, for some rules, a very strange evolution emerged out of nowhere! Wolfram just like anyone else was baffled by the complexity of them. These patterns were very random, complex and without any repetition or oscillation. Rule 30 was one of them:
Even imagining this much of complexity out of a simple rule seems impossible. The interesting fact is that you can’t reduce this complexity to simpler parts because the models are so utterly simple themselves. Rule 30 is a complexity atom in our world. An irreducible complexity form! As you go down the rule 30 you see more and more new patterns, it is as if rule 30 never cease to amaze you with its patterns. Even though Wolfram realized this visually but later on two other mathematicians, Kudson and Devaney proved [3] mathematically that rule 30 has the “sensitivity to initial conditions” and “complexity” properties.
There are other rules that exhibit complex behaviors very unique and different from rule 30 like rule 110 and rule 184. You can see these patterns that emerge in nature. One great example is a seashell fish named conus textile.
We can see them in other seashells with even more diversity:
Rule 30 is so random that Wolfram used it in Mathematica for producing random number generators.
For rule 110, it is proven that it is computationally universal, that means you can use it as a Turing machine to compute anything and this means they are small computers theoretically capable of any forms of computation(but not necessarily the most efficient ones). This also amplifies the “simulation hypothesis” that proposes all the reality, including earth and universe, is a computer simulation. The cellular automata show that for having computers you don’t need finely tuned parameters that were adjusted by a creator, these simple systems are so simple that can emerge out of randomness!(consider the fact that the probability of rule 30 to emerge is just one in 256 which is too large!!).
To summarize, we can say complexity theory is a young science and there are so many things that yet to unravel. But what is clear now is that:
The old premises about the scientific approach are no longer hold. Complexity is not always reducible. Complexity doesn’t neccessary needs a creator nor fine tuning. Complexity is at the heart of nature but it took us a long time to see it right in front of us. The atoms of complexity are everywhere!
The next time you look out your window to the street, you have a very different perspective on the birds that fly and even people who walk and interact with each other.
References:
[1] Manukyan, L., Montandon, S. A., Fofonjka, A., Smirnov, S., & Milinkovitch, M. C. (2017). A living mesoscopic cellular automaton made of skin scales. Nature, 544(7649), 173.
[2] Shiffman, D. (2012). The Nature of Code: Simulating Natural Systems with Processing. Daniel Shiffman.
[3] Cook, M. (2004). Universality in elementary cellular automata. Complex systems, 15(1), 1–40.