Posts Tagged ‘Cellular Automata’


December 20, 2016

The other day, a friend and I were discussing various jewelry items that we liked. They showed me pictures of ones that they liked, and I looked through various lists and found ones that I liked, and they expressed some amount of surprise at my choices. In most of my life I tend to appreciate things that are simple, and kind of stark in appearance as far as aesthetics go, and the items I chose, to this friend, did not seem to fit this pattern, being items with many repeating patterns and what seemed to be a not insignificant amount of complexity. When they said this however, expressing a surprise that I would like the more complex or complicated designs, I felt there was something wrong with the statement, as these did not seem to me to be as different to me as the simple designs they had assumed I would like. I told them then, that I grew up reading “Where’s Waldo?” and that the patterns seemed kinda zen to me, simplicity hidden in their seeming complexity. After the conversation was over, I thought back on the conversation, and the statement I made, and I was not sure I had quite expressed my feelings about beauty in simple complexity, something I hope to do here and now.

When I spoke of “Where’s Waldo?” my mind was thinking not just of it, but of a number of other things that were connected together in my mind along with those books. I was thinking of tessellations in art, repeating motifs based on drawing the same shapes over and over again, interwoven with themselves. I was thinking of a concept from computer science called the cellular automata, and I was thinking of elegant computer algorithms which generate complex interactions from simple rules. All of these things to me seem connected, and all feel to me, as though they are fundamentally elegant and simple, even if the end results seems large and complex. Let me walk you through a few of these thoughts and see if I can show you why they all feel similar to me.

Fundamentally I really enjoy patterns. While I was in school, I was never a great artist, but I took a number of art classes, and the one thing that stuck out about my art, which was typically rather mediocre, was my use of patterns. I would draw pictures and then fill in each part with a different pattern, whether it be a hundred tiny stars, endless dots, lines, hashes, squares, waves, whatever. I would feel quite content spending long periods of time simply filling in blank spaces with repeated shapes and designs. And it would not just be repeating patterns either. I would occasionally enjoy drawing expanding patterns, where something starts simply and then follows a progression, growing larger and more complex following simple rules. In each of these cases, even though the piece might take a long time to draw because of the need to draw many many little bits, when it was complete, it would look unified and simple, and in my own mind at least, beautiful.

This love of patterns extended to math classes, where one of my favorite topics was finding and extending patterns in numbers. Like seeing that 1, 2, 4, … would go on to 8, then 16, or that 3, 7, 19, 55 was tripling each time then subtracting two, and thus would go on to 163. Finding the pattern in numbers, especially when it was more difficult, and initially appeared random was something I enjoyed a great deal. It always seemed to me that the fact that you could explain an infinite sequence of numbers in a few words, and thus understand the whole thing that way was incredibly powerful. I was always quite good at finding the patterns and would always do extra problems just for fun when the unit on that subject came up. Later in life these sorts of patterns of numbers would come up again in my computer science courses, when I learned about recursion and patterns such as the fibonacci sequence: 1, 1, 2, 3, 5, 8, … where each number was found by adding together the previous two. I enjoyed it there as well, able to use computers to think about and examine changes in the string of numbers based on simple changes to the rules of the patterns.

As I learned more about computer science I got to see and use even more ways one could generate very powerful and seemingly complicated results from very simple inputs. The flocking of birds, a pattern that seems somewhat random, but has its own special sort of movement can be programmed into a computer with three simple rules. The solution to the game Tower of Hanoi, where you have a stack of increasingly large rings around one of three pegs, and your goal is to move the whole stack to another peg, while only moving one ring at a time, and never putting a bigger ring on top of a smaller, has an exponentially increasing number of required moves as the number of rings increases. The solution to all sizes however, can be explained to a computer in something like ten lines of code. Coding itself has a certain aesthetic to it, in which a solution is considered more beautiful and elegant if it solves the problem in a few easy line of code, while solutions in which one has to write things out, explaining each of the possibilities to the computer in excruciating detail are considered less elegant and feel much less nice to program. And one of the ultimate examples of this, of getting incredibly intricate and interesting things out of something incredibly simple is an idea called the “cellular automata”.

Cellular Automata come in many forms. The most famous example was invented by a man named Conway, and is called the Game of Life. It takes the form of field of black and white squares, with the black squares representing life, and the white squares being empty. You can start the scenario with any combination of black and white squares, and then, over time, the black squares live and die based on simple rules based on how many other black squares are around them. A square will be “born” in a white square that is touched by exactly three black squares, and a black square will “die” if it is surrounded by more than four, or less than three black squares. With only those two rules, a simple grid of squares will change, growing and moving and dieing and forming patterns in a fashion that can really only be described as life-like. Whole hosts of mathematics problems have been explored within the confines of this incredibly simple system, and it was proven that it was possible to construct, within a system containing only a grid of black and white squares and two rules as to how they change, a turing complete computer, which means that, given sufficient time, such a pattern could solve any problem that any modern computer can solve. But even the Game of Life is more complex than some other cellular automata. Lets take a look at basically the simplest possible automata, the one dimensional ones.

The game of life is a two dimensional automata, as it uses a grid of squares that changes over time. One dimensional automata only use a single long line, not even a grid. As such, the simplest version of these automata only have three inputs. They can look at their own color, and the color of their two neighbors, on their left and right, and use that information to determine if they will be black or white on the next turn. With three different inputs that can be one of two colors, that means there will be 2^3 or 8 different combinations of inputs, and since you can choose either black or white for the output for each of these eight different combinations, this means that in total there are only 2^8 or 256 total one dimensional cellular automata. Let me give you an example of one. This is number 184.

If it and both its neighbors are black, designated BBB, then the square stays black. If its left neibor is black, and it is black, and its right neighbor is white, designated BBW, then it changes to white. BWB, or both neighbors black and it white, then it changes to black. BWW changes to B. WBB: B. WBW: W. WWB: W. WWW: W. And that is the rule. Lets take a look at it in action.

Lets start with one black square in a long line of white ones. WWWBWWW. That’s our starting spot. Since we know that white surrounded by two other whites will stay white, we can know that we can ignore all of the pattern except for the parts right next to the black square, because they will not change. The square to the left of the black one has white on its left and black on its right so its pattern is WWB, which means, if we look above, that it will remain white. The black square meanwhile is surrounded by two whites which means its WBW which goes to white. The square to the right of the black one meanwhile will change to black because it fits the pattern BWW. So if we update everything, the only thing that changes is that the black square goes to white and the square to the left of the black, turns black. So our pattern changes to look like WWWWBWW. If we look at a few generations it will look like this:





Basically, the pattern is simple here. By looking at it over time, the black square moves one to the right each turn. Not much complexity there. It gets more fun with more than one black square. The pattern still ends up moving all black squares one to the right any time there is a white space there for them to move. If there is another black square to the right though, it pauses for a turn, staying in place, and only moves on when that black square has moved on. As it turns out, this pattern ends up modeling traffic in a single lane road. If you think of the black squares as cars, they move forward when no one is in front of them, and then break when another car is right in front of them. This simple pattern of the relation between three white or black squares lets us learn interesting things about traffic patterns. As it turns out, if the density of cars is less than fifty percent, ie if a road has enough room for a car length between each car, then after a bit, traffic will unjam and all cars will be able to go full speed. If its greater than fifty percent though, the familiar pattern of the traffic jam emerges, with stops and starts. Using the model from this pattern its actually possible to figure out how fast the cars will end up moving compared to the speed they could move without having to stop. Obviously its not a perfect model, as it leaves out a lot of the complexity of the real world, but you can learn real things from this model.

So that’s pretty cool, we took a simple pattern and were able to learn something about the real world from it. As it turns out, this one pattern actually can model two other real world things as well. By interpreting the black and white squares differently, its also possible to model how sediment accumulates in hills and valleys, as well as modeling the movement of positive and negative particles which annihilate one another when they collide. This one pattern can do all of that. And its not even the most interesting of the patterns. Pattern 90 can be used to represent how trees can grow depending on availability to sunlight as well as creating a triangular fractal, while Pattern 30 creates something close to pure randomness. The most interesting of all however is Pattern 110, which was proven to also be turing complete, just like the game of life, capable of computing anything a computer can compute. A relationship between three black and white squares can compute anything computable.

Anyways, that was a fun digression, but basically, I find things created out of simple rules and patterns to be beautiful. As long as explaining how to make it is simple, I consider the thing itself to have the elegance of simplicity. Hence why I like patterned jewelry and was a bit confused when my friend expressed surprise in my choice, as I consider those things fundamentally just as simple as something that’s appearance is more straightforward. I also did a bit of thinking about my initial example of “Waldo” and I think those books are a bit different than the kind of simplicity I have described here, so I think I’ll do another post about that at some point soon. Anyways, this was just me talking about why I think certain things are elegant or beautiful, simple, even if they appear complex.