Exploring cellular automata 2 — my lovely maggot children

In some other post I linked to the Wolfram “atlas” of 1-dimensional elementary cellular automata, the list of 256 rules that can apply to a row of “on” or “off” pixels to determine a successive row, in which a pixel’s successive value is only dependent on its own and those of its two neighbors. There are only 256 of these because of this limitation.

We can extend this to a 2-dimensional space. This seems to be easier to follow what’s going on — maybe just by the nature of looking at a computer screen. It’s the space that the Game of Life lives in. A grid of pixels can be on or off, and a successor grid follows, with each pixel’s state determined by its initial state and those of its neighbors. In order to visualize this, you could lay each successor on top of its parent grid to make a 3D object (analogous to forming a 2D image for a 1D array of pixels). But this would be really hard to look through. Instead, just play each image after its successor as an animation.

Stable_puffer_animation.gif
A puffer in Game of Life. Each frame of the animation is a new epoch. Needless to say, this isn’t an obviously possible construction given the GoL rules. Wikipedia
Conways_game_of_life_breeder_animation.gif
A GoL breeder. This configuration only creates guns, which create glider spaceships. In the last frame, the breeder is colored red, the guns green, and the gliders blue. Bickibeepia

A ruleset can be described with a series of images, like the 1-D automaton, but again, you’d have to either stack the start example on top of the resulting center pixel, or place them side by side. In addition, there are going to be many more images necessary for a rule, as there are more configurations of on-and-off neighboring cells in 2 dimensions.

This also introduces the uncertainty in what a neighborhood is in 2D. We could consider the 4 cells in the cardinal directions as the only neighbors (the von Neumann neighborhood), or we could tack on the corners, too (the Moore neighborhood).

CA-von-Neumann.png
The von Neumann neighborhood. Pink cells show an extended version.
CA-Moore.png
The Moore neighborhood. Wikibleedia

For the von Neumann neighborhood, each rule alone would require 2^5 = 32 images. With a choice of on or off for the resulting cell for each image, there are 1024 elementary cellular automata. Not a bewildering number, but still a lot.

vonneumannex1

vonneumannex2
Two examples of rule icons for an elementary cellular automaton using the von Neumann neighborhood. For a single ruleset, one would need 32 of these bad boys. These read a bit differently than the 1-D rule icons — the square on the right replaces the center square in the image on the left.

The Moore neighborhood would have 9 squares, replacing the center square, and so one would need 2^9 = 512 icons for each rule. There are 512^2 = 262144 rules of this type. Yikes! There are the same number of squares in the “extended” von Neumann neighborhood, so these numbers apply there as well.

mooreex.png
A single icon of 512 from one of the elementary automata using the Moore neighborhood regime.

Both of these neighborhoods are probably characterized completely — tracking a few of the properties of 263000 systems doesn’t seem to be out of the realm of possibility, especially when considering that this number can be reduced by a factor of due to horizontal-mirroring, vertical-mirroring, centerpoint-mirroring, and color-inverting of each of these. So, the 512 in the 5-cell neighborhood reduces to only 64 with unique behaviors, and the 9-cell neighborhood reduces to 32,768.

What seemed exciting was to look at larger systems. A Super von Neumann neighborhood of 21 squares will have 4,398,046,511,104 rulesets of 2^{21} = 2,097,152 icons each, and the Super Moore neighborhood of 25 squares has 1,125,899,906,842,624 rulesets of 2^25 = 33,554,432 icons each. Now we’re having fun.

extendedvonneumann.png
The Super von Neumann neighborhood of 21 squares.
extendedmoore.png
The Super Moore neighborhood.

It felt like there was some chance of picking something weird out of here.

A ruleset based on an oscillator

One contruction I didn’t mention in the last post was an oscillator — a repeating, unmoving pattern. Some oscillators can be seen in the wakes of the dirty puffers.

2x2_p2s.gif
Some period-2 oscillators in GoL. Bumbobedia.
Koksgalaxy.gif
A larger oscillator, with period 8. Bunklebeepia.

Oscillators are emergent in GoL; there isn’t anything about the rule that explicitly reflects an intent of repetition. I was interested in making a rule that was based on an oscillator, and to see if something like spaceships would emerge.

Maggotworld

The simplest oscillator I could think of that seemed interesting was a clockwise spinning line. 3 activated cells, with a diagonal between the first two, would appear to spin around in a circle. If there were three cells in this configuration, the next epoch would deactivate the cell in the back, and activate a new one in the next step around a circle. This resulted in an 8-period oscillator. I originally called the idea Spinworld, but it soon seemed appropriate to call it Maggotworld.

oscillators.gif
Four base oscillators (maggots) in Maggotworld with different phases. White pixels are considered activated. The base oscillator has a period of 8 epochs.

Instead of matching the Super Moore neighborhood around every pixel with one of the 33.5 million in the ruleset, the maggotworld propagator just checks if there are three activated pixels in the right configuration nearby to turn on. There are eight ways this could happen — corresponding to the eight squares that are activated throughout the cycle. This doesn’t mean there are only eight icons of the 33.5 million that lead to an activated central pixel. The pixels toggle; a dead pixel toggles on if there are one, or three maggots approaching it. It toggles off if there are two or four approaching it. The same is likewise true for the tail ends of a maggot — two maggots with the same tail will leave the tail point on, as it is toggled twice. So there are many ways pixels could be left on or off depending on the situation. This seems ripe for emergent behavior!

I ended up trying a bunch of different setups to see how they behaved way back in April, and wrote most of the above then, but haven’t gotten around to this showcase until now.

Random starts

I began by just slapping random starting configurations down and seeing what happened.

1.png
The seed…
2.gif
…and the result. My optimistic dream of seeing spaceships shoot out into the black shattered.
randomstart.png
A high density of activated squares…
randomstart2.gif
…is quickly lost after the first epoch, leaving just a few maggots wallowing in their filth. Some of these are neat.

After some initial discouragement, some neat patterns did emerge. In the last animation you can spot a few figure 8s, figure triple-Os(?), and maggots passing straight through each other. Not a spaceship, but at least something a bit more complicated.

splotchesanimreal1.gif

Not so random starts

If I couldn’t get a spaceship out of this, I could at least look for something cool. Time to get systematic. I placed maggots at varying relative phases and positions to start and let them go.

7.png
Two maggots 180 degrees out of phase at varying relative starting positions.
8.gif
And the results.
allstartingpositions.gif
All the same with different starting phases.

This was a bit discouraging — none of the ones that touched made any lasting patterns beyond a single oscillator. Anything interesting would have to be made of more than 2 of these, or have some stationary gunk waiting around to push them around a bit.

In one of the random setups, I saw this little friend, which I’ll call a slingshot oscillator.

slingshotstill.png
Slingshot oscillator.
slingshot.gif
Slingshot has a period of 14.

It’s got a period of 14. Having a different period is… useful? How is any of this useful? I dunno whatever.

Another neat result would be to get a pattern that turns on cells outside of the normal oscillator radius. Here’s one. It looks like a really low resolution hand-style cursor. Let’s call it the flinger.

flinger.png
Flinger start!
flinger.gif
Flinger go! It turns on a cell in the upper right well outside of the original oscillator’s domain.

The last thing of this type is a little u. I like this because, while it seems like these rules easily reduce the number of lit cells, this generates an extra sixth cell by the end of its process.

uthing.png
U-thing!
uthing.gif
U-thing go!

Behavior in grids

If I couldn’t get a spaceship flying away in empty space, maybe I could get something neat with stationary patterns placed ahead of time. I started by plopping oscillators in a lattice of lit points. It’s real easy to get some ongoing domino action this way.

grid1.gif
Diagonal motion.
grid4.gif
A couple more.
grid2.gif
Vertical motion. There’s a lot of trash left behind, but the key to see here is that only one or two lit squares next to a lit bar drives the motion. The lit side determines which way it travels.

Trams and fuses

The last one looked neat. I tried to make more “trams” following a track. Here are a bunch. There are also configurations that rip the track apart. Let’s call em fuses.

trainsandtrams.gif
“Trams”

Some of the styles are repeated with a hole in the track to show how they deal with that. Holes are also placed at different locations along the track for the same style of tram to show off how they travel: trams hop two spaces at a time, not one. An “oddly” placed hole will force it to reflect or scatter differently than an “evenly” placed one.

I was taken with the self-repairing track on the bottom.

trainrepair.gif
Self-repairing tramtrack.

This seemed like a way to create a caterpillar-like spaceship of indefinite length that scootches forward a couple squares each cycle. I wasn’t able to figure how to get it to repeat, thought.

Another fuse had an end that, after some acrobatics, sent another tram that flipped the orientation of the fuse.

trainwithflipper.gif
A single lit square between the tracks flips the sides of the track: two lit on top and one on the bottom become one on the top and two on the bottom.

Timers

One last thing and I’ll let you go, I swear. A row of lit squares can be used as a timer of indefinite length. This could go up above with the other oscillators, but the fact that this can be stretched to as long as you need it puts it in its own class.

timer1.gif
A timer. This repeats. It takes some time to do that so I called it a timer.

These can also take a turn. These turns could be used to stop the motion, or to initiate the timer in the first place:

fuse.gif
Two timers. The top timer is initiated after the maggot turns the corner. The bottom stops after the path has been traversed.

Maybe these are more appropriately called fuses? But I already used that word.

Showing these little tricks and behaviors is interesting enough alone for me, but it would be really swell if we could figure out how to produce oscillators / timers of truly any period. I’m also still wondering if there is an elusory spaceship, one without a grid or track to support it, hiding in these rules. The holy grail after that is to get these things to do binary logic, but let’s save that for another day.

I Lied

I said I had only one last thing but I totally lied to you. You must be feeling pretty silly right now! Just one more bit. I promise. 🤞

Before finishing up with the maggotworld animations, I had tried a lot of different rulesets to see how they’d act. One of them was simple: A cell would turn on if it had an odd number of neighbors (in the Moore neighborhood), and off otherwise.

Fredkins.gif
Fredkin’s Replicator.

What a pretty pattern! I was pleased to learn later that I had recreated something called Fredkin’s Replicator. You can see some explanation in Numberphile’s Terrific Toothpick Patterns (starting at 14:20). A lecture also by Neil Sloane gives more insight into analyzing this and other “odd-ruled” cellular automata. Do yourself a favor and check out at least the Numberphile vid.

Fredkins.png
The Fredkin’s replicator having reached the 63rd generation. What a beaut! You can see the same repeating structures, and the same shapes repeated at different scales.

Exploring cellular automata 1

Conway’s game of life is maybe the most well known ruleset for cellular automata. Each cell in a grid has some possible set of states, and set of rules for changing state based on its own and it’s (usually) immediate neighbor cells. Time elapses with a number of discrete steps, sometimes called epochs. In Game of Life, a cell can either be “alive” or “dead” (on or off), and will live for the next time step only if it has one or two alive neighbors.

Some incredible patterns emerge, including spaceships, guns (creating gliders and spaceships), breeders (creating guns), other puffersrakes, long-lived methuselahs (this example creating some gliders).

Other rulesets lead to neat patterns. Here’s a fun one with many cell states. It lets you rate the results as it scans some starting parameter space.

So, we’re certainly not limited to one ruleset. Coming up with one is easy — finding if there are any neat patterns maybe not so much. It might be better to first explore simpler rules — ones in only 1 dimension. In this case, a linear space is segmented into cells, and each cell has only two neighbors. Given some configuration of three cells in a row, the middle cell’s state in the next epoch will be dependent on its own state as well as the two alongside. When considering how to change any cell, since there are only three cells to consider, and only two possible states for each, there are only 2^3 = 8 arrangements to consider when changing any cell. Because of this small number, it’s no problem to display the rule of the automaton as a list of diagrams, each showing one of the eight starting arrangements and the resulting state of the middle cell in the next epoch.

The rule icons for Wolfram’s “Rule 73”, one example of the 8 diagrams needed to completely describe this cellular automaton. To determine if a cell is on or off in the next epoch, compare it and its neighbors to the icons, and find the one whose top row matches. The cell beneath in the icon indicates the state of the cell in the next epoch.

With some initial state, for example:

initial73.png

The next line is produced by scanning over this line and matching the top row with the one from the rule icons.

Rule73.gif

Note that this wraps around, connecting the two edges. This process then continues indefinitely for successive lines. We’re free to pick any length of line and any arrangement of on and off cells as an initial condition, but once this is done, the rest is automated. This particular initial condition for this rule ends up looking like this:

rule73.png

This is kind of neat, but these processes don’t get to show off unless they’ve got some room to work with. Here’s the same rule applied to an initial state of a single black cell in a long row of white.

The repeating triangles are a pattern characteristic of some of the more interesting rules. Rules 30, 90, 110, and 184 are supposedly the most cited in scientific or mathematics articles.

Because there are only 8 arrangements of cells we need to specify to determine a 1-D ruleset, and each arrangement offers the choice of the middle cell turning on or off, there are 2^8 = 256 possible rules of this type. You can see links to them all here. One could argue there are only 128 rules, 64, or even 32, since negating all the colors, taking a mirror image, or negating the mirror image doesn’t change the behavior much. This means each rule is one of a set of four that operate in the same way.

I’ve already linked to the Wolfram Atlas a few times. The images above were taken from there or made using Mathematica. Stephen Wolfram, of Mathematica fame, is also well-known for his work on cellular automata. He’s argued that these things may be more fundamental to nature than mathematics. It’s considered controversial. I haven’t read A New Kind of Science, a book where he lays this all out, but it’s free and online. Maybe worth checking out. It seems like some of the argument hinges on the fact that some of these automata are Turing complete — they can be set up to operate and produce results like any computer program.

I’d just like to note that my interest in cellular automata is based pretty much entirely on having fun. It’s 11 o’ clock on a Saturday night.

A step after checking out the 1-D rules is to explore the 2-D rules. Next I’ll show off a rule and try to do something interesting with it.

Pareto Principle

The fractal drawing period went well enough. I suggested to the students that they instruction sheets increased in difficulty (when in the same order as in the previous post). I expected most to go for the Sol LeWitt drawing. In fact, that was kind of a wash! I had really hoped to have a nice full sized Wall Drawing 797 poster made by the kids. Most went straight for the dragon fractal. I can’t really blame them, since it looks so cool, but my instructions were unclear enough to make it difficult for most. The biggest issue was that most students didn’t pick up that each “elbow line” needed to be drawn so that it connected opposite corners of the squares on a piece of graph paper. Their dragon drawings ended up looking flat and floppy, and after only a couple iterations there wasn’t a whole lot left to work with.

Most of the kids were not thrilled to be doing any mindfulness activity. Many asked if I could ask the administration to never have a mindfulness advisory day again. There were, however, a few who quietly and attentively worked on drawing the curves, and a couple did quietly exclaim that the dragon curve was pretty cool.

I’ll keep things in perspective. My goal wasn’t to make them experts on drawing these figures, but to at least expose them so that they can recognize the ideas if they happen to come across them later. I’d also hope that a seed of interest has been planted in at lease one student, so that they’d be motivated to read a bit more about these things on their own.

The ratio of interested kids to uninterested kids reminded me of something called the Pareto Principle. This rule of thumb asserts that, in a situation like this, I could expect 80% of the effort or participation to come from 20% of the students.

This is a really lousy model for the drawing activity, not only because effort isn’t a well-quantified value. Number of drawings, time spent with pencil to paper, some arbitrary standard for quality all could play into the measure of effort. In addition, the “4:1 for 1:4” Pareto rule is a goofy way of putting it; the statement that “20% do 80% of the work” can make one think that there are some students who are doing 4 or 5 times the work of another. In fact, it would mean that the hard-working students would be doing 16 times more than one from the larger population. This seems a bit high for a typical high school class.

paretoprinciple
An example of the Pareto principle for a group of five students making identical drawings. One student (20%) ends up making 16 / 20 = 80% total drawings.

The Pareto rule might work a bit better in the business example, “20% of your customers will give you 80% of the sales,” but any decent business would hopefully make predictions based on their particular situation and history. Perhaps most hover around this distribution — it doesn’t seem too wild of an idea that a few die hard regulars are the ones keeping any given bar afloat.

The real benefit of this rule of thumb is to give that sense of perspective. It would have been unrealistic for my goal to have the room be lit with energy, all of the kids scrambling around in excitement because they were given some drawing instructions.  To expect 1/5 of the students to be truly interested might sound pessimistic, but in retrospect it’s a good place to start when making expectations. It might also be a good place to start in a brand-new business.

The rule is an instance of a Pareto distribution, which is a generalization that would be able to tell you exactly how much each student is producing (rather than big groups), as well as describe groups of students who are producing work at different ratios than 4:1. The benefits of being able to describe your system (be it schoolchildren, sales, volunteer participation, whatever) with a Pareto distribution would not only lie in how accurate the shape is, but also in knowing exactly the parameters that fine-tune that shape.

The Pareto concept has other ways of showing itself. Zipf’s Law says that you order the words in the English language by how often they’re used, the Nth word in the list will be 1/N as popular as the 1st. So, you see a very small number of words showing up a very large percentage of the time in writing. Like the Pareto principle, this is a generalization, and different people, regions, and documents will have variations on word popularity. These variations allows for statistical stylometry, as well as making sure every book in the library isn’t identical.

The Internet %1 Rule (or 1-9-90 Rule) is one that suggests that only about 1% of users on a website actively create content for that site. This doesn’t mean 1% of people who read BBC.com are writing news articles, but it might mean that 1% of a news site’s readers are leaving comments. I’ve heard this referred to often in the realm of podcasts, where show hosts can expect about 1% of users to email in, or participate in a contest, etc.

Again, it’s key to note the error bars we’re willing to accept. If 2% rather than 1% of listeners responded to a call for podcast questions, the creators might not notice the difference. Using the Pareto principle as a very rough rule of thumb, as a suggestion for what to expect, is the way to make it work for you effectively.

 

Fractal Drawing for Mindfulness Activity

Tomorrow, our student advisory team is leading a school block dedicated to mindfulness. Each teacher leading an advisory was asked to propose an activity that would promote mindfulness.

I put together the following four sets of instructions for kids to sit and do focused drawing for the period.

walldrawing797

Sol LeWitt: Wall Drawing 797

hilbert4

Hilbert Curve

peanocurve

Peano Curve

dragon

Dragon Curve

 

My experience with very short meditation sessions before and after kendo practices are the most direct form of regular mindfulness of which I’ve been a part, at least as a designated “activity.” I’m not prepared to lead 45 minutes of quiet meditation for high schoolers, though, and especially not if I have to keep them in pain sitting in seiza. I like to think my time hiking in the Adirondacks has been mindful, in that it involves focus, physical energy, awareness of one’s surroundings and situation, as well as the calming connection to nature, but I can’t take the kids out on a tough hike for a half hour in the middle of the school day. Exercise like running could be mindful, but it sure isn’t when I go, since I’m usually listening to a podcast or music while I jog. Really, the request to guide a session caught me off guard, since I don’t think I’m qualified to say or present much about mindfulness.

The other activities the teachers are leading include Drop Everything and Read, yoga, “games outside”, adult coloring books, and exercise. These all seem like they could be done well enough.

I figured that, since I’m preoccupied with math while at the school anyway, I might as well try to fit in some kind of math-related thing. The fractal curve drawing stuff is something I brought up while co-teaching a Math and Art elective at a previous school, and it had already been floating around in my head while thinking about leading a math team, or introducing some kind of alternative project for one of my current classes.

Sitting down and scratching away a pattern that follows a rule, and knowing it’s going to end up with a near image in the end sounds like a great relaxing time to me. I do have to remind myself that sometimes my brain is a runaway freight train, and people may not be so interested in thinking about Star Trek or Homestuck as much as I want to keep bringing them up. The idea that someone might not be as interested in drawing fractals for an hour as me is something I need to be aware of. I do think there’s a good chance this set of activities will activate the LEGO loving kid in some of them, though.

While sitting in a meeting, I realized the dragon fractal could be generated by recording a list of L and Rs, representing left and right 90-degree turns while drawing a line in a grid. Start with just an L. For each iteration, add an L to the end of the string, then write a mirror image of all of the previous letters: write them in reverse order, and replace L <—> R.

L

L L R

L L R L L R R

L L R L L R R L L L R R L R R

L L R L L R R L L L R R L R R L L L R L L R R R L L R R L R R

etc. These five strings correspond to the images at the top of the Dragon Curve drawing instructions. The mirror image behavior creates the self-similarity. It also made it more clear why the paper folding method creates the same figure.

Later I realized that this set of instructions is essentially the same as the Lindenmayer system of writing the dragon fractal. Let “F represent drawing a line forward, “+” a 90 degree counter clockwise turn, “-” a 90 degree clockwise turn, and “X” and “Y” as placeholders which add to the structure but don’t indicate a drawing instruction. Start with FX as your string of drawing instructions. For each iteration, replace

X –> X+YF+

and

Y –>−FX−Y

You can see the mirror image instruction here: the string to replace each “Y” can be recreated by taking the X replacement string, reversing the order, and swapping X <—> Y and “-” <—> “+”.

In the case that fractal drawing is too intimidating for anyone, I’ll include the Sol LeWitt page as well. I hope we can beast out a full posterboard with 797-like drawing tomorrow as a class taking turns. The MASS MoCA trip mentioned in the instructions was with a bunch of good friends in August, and they drove a conversation about the piece that day, and continued to think and play with it for some time afterwards (Phil and Ben’s blog posts, each with some neat insights and programming results, can be found in the links <— over there and <— over there).

We’ll see how tomorrow goes.