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.

Thoughts and speculation on Star Trek’s popularity

1200px-raumschiff_enterprise_schwarz-svg

It may be possible that I have thought of Star Trek more than half of the days I’ve been alive. Those days are also pretty skewed towards the second half of my life as well. Is this much of a feat? Sometimes I will think of people or places that have been important in my life, and I’ll take pause to wonder how many weeks or months it’s been since I last thought of them. I’m not sure I have the same issue with this TV show. Plenty of entertainment is manufactured to stick in our minds.

People who like Star Trek can seem pretty evangelical for a bunch of humanists. This comes with any fandom, but it’s a special thing to be able to look at the culture surrounding the show that is often considered the originator of the modern fandom. It might be ridiculous to say that fanzines and fanfiction, slash fiction and shipping, conventions and cosplay were all created from this one 3-season show. People published and shared stories about their favorite characters beforehand, I’m sure. I’m also sure that plenty of these were a bit sexy, played with taboo, and featured author-insertion (no pun intended). Theatrically or historically minded folks dressed up and played parts for their own sake. Interestingly, one of the first major renaissance “faires” was in 1966, the year ST debuted, at the Paramount ranch (although Paramount did own the rights to broadcast the show until 1969). But Star Trek does seem to be a major popularizer for these ideas, and set up some expectations about things like anime conventions and unwritten rules about how to write yourself doing some cool kissing with Matt Smith without receiving too much judgement.

Part of the continuing success of Star Trek is due to its popularity. It’s a franchise, and success leads to success. It’s a household name.

There must be original things that originally led to its popularity, though, and keep it going. It boils down to the following.

It drew from established genres that were underserved and added to them.¬†Gene Roddenberry drew inspiration for Captain Kirk from the Horatio Hornblower novels. I haven’t read these, but it seems that they themselves heavily draw from the fetishized “plucky” character type and high adventure of (boys’) Victorian-era novels and subsequent pulp fiction. In addition, the space-adventure theme of the show probably drew in a lot of grown-up boys who used to read Tom Swift, Flash Gordon, and still looked fondly back on watching Captain Video. The Twilight Zone, and other “short story” format science fiction shows existed beforehand, but it seems they didn’t have the draw of a character connection.

This is the awesome benefit of having a show based on an indefinitely fast space ship. You can have an episodic format which allows for missing a broadcast and still following the story, like a sitcom, but offers a way to feature completely different premises as often as the creators want. This gives more freedom than a sitcom, which returns to the status quo at the end of every episode, and also keeps the same neighbors around.

Star Trek wasn’t really a huge hit except with a vocal minority (you could spin as an example of¬†the Pareto principle) until in syndication, after its cancellation. The Next Generation series wasn’t exactly a hit right off the bat either. But, funnily enough, it likely benefited from a similar drought of science fiction on tv, only a couple decades later. The drop in popularity (and as many others say, quality) of Star Trek in the 90s, as Deep Space Nine, Voyager and Enterprise continued on, was likely an indirect result of TNG’s popularity: the new Star Trek spawned a new interest in the genre. We might not have seen Babylon 5, Stargates, The X-Files without it, but these might have also saturated the market.

It straddled the lines of being interesting, silly, and thoughtful. Again, Star Trek wasn’t a huge hit at first, but the new-setting-every-week bit was attractive to the science fiction short story lovers. These types are usually looking for ideas that will stick with them for some time afterwards. The ending of The Twilight Zone I’m sure left a hole that Star Trek was able to fill. These ideas were social and political commentary, either unspoken or explicitly stated, or technological and scientific. Deeper personal stories wouldn’t start until the first movie, and The Next Generation, and the political intrigue wouldn’t¬†really pick up until later seasons of TNG (and DS9!).

Viewers at least had¬†some characters to count on week after week. Again, this could have attracted the pulp lovers who fondly remembered reading the Hardy Boys or Nancy Drew (although I’m not sure the Hardy Boys were giving the die-hard fans¬†homoerotic suggestions in the first year of publications). These characters served as the much needed “human” connection that short stories tend to lack — having seen them week after week raises the stakes when they find themselves in peril.

The thinly veiled suggestions of a romantic or sexual relationship between Kirk and Spock brings us to the common assertion that Star Trek was intentionally camp. It’s come to my attention, after seeing Whatever Happened to Baby Jane? at our little Fancy Movie Night, that at the time the camp aesthetic was becoming more popular on television as well as in film. By the way, this might also owe itself to the popularity of Some Like it Hot, also seen at FMN, a film which served to help dismantle the Motion Picture Production Code. The effective removal of this explicitly written code made it a lot easier to play around with the potentially gay relationship, which allowed the creators to bring in other campy qualities.

The title of this section isn’t to suggest being gay is silly, but it may have appeared so to a typical viewer. In addition, the camp aesthetic definitely connected lightheartedness with homosexuality.

Finally, and maybe most obviously, the show was entertaining on a surface level. The traditionally boyish interests of seeing the ship fly around, shooting ray guns, goofy aliens, funny and sexy pajamas, and brawling action I’m sure solidified the interest of plenty of people (and not just boys).

But the thing people like to talk about the most nowadays is…

It introduced a progressive cast of skilled officers and regularly gave social commentary. This is the part that remains the most inspiring. I wonder how essential it was to the show’s initial popularity, but without these aspects, the show would certainly be a lot less interesting, and definitely not worth getting worked up over 50 years later. Having a collection of Earth’s races all working together on the same bridge, backed by Roddenberry’s vision that they have moved beyond interpersonal conflict, stands as a great source of inspiration. In addition to the obviously racial statements, the addition of the Russian Chekov in later seasons, although he was largely there for comic relief, represented a promising future (respect, as well as existence!) for what had been the United States’ chief enemy at the time. (I’ll have plenty of chance in the future to chat about the other representations of the USA’s enemies, the Klingons and the Romulans.)

Human progress was not only shown in social achievement or technological power. Spock himself was often played for laughs due to his rigidity and failure to acknowledge his (clearly present) humanity. Although loved and respected by fans, Spock often was a straw man representing the emotionally bankrupt, completely unempathetic man struggling to maintain feelings of superiority based on knowledge and critical thinking. I think if Spock were a character created today, he would be compared to “mansplainers” or Red Pill types. The fact that the other characters can explain their choices outside of Spock’s coldness, and make fun of him when he lets a bit of emotion shine through, promises a future in which people don’t have to be miserable pedants who only care about things for their academic value. The human still has a place in the 23rd century. We don’t have to replace ourselves or mimic machines as time pushes forward. People liked this idea.

 

I’ve been thinking about Star Trek even more than usual lately, what with the first episodes of Star Trek Discovery airing last week. I’ve got even more to say about that, but perhaps it can wait for another day.

The Image Superiority Effect and The Baader-Meinhof Phenomenon

Last year I came across what was at the time a popularly shared image listing cognitive biases (found at the bottom of this Medium article). The graphic originally reminded me of¬†An Illustrated Book of Bad Arguments, which I had picked up along with Randall Munroe’s¬†Thing Explainer, maintaining a general theme with my purchase. The Book of Bad Arguments unfortunately didn’t turn out so great: the illustrations are sort of cute sometimes, but are more often a bit awkward and rarely illuminated the logical fallacy they were attempting to explain. In addition, the written explanations themselves were not brilliant, and I’ve also come to find that a couple descriptions were just plain wrong.

I¬†do¬†highly recommend the Thing Explainer. It takes the cute and informative style of Munroe’s¬†Up Goer Five¬†and fills a book with it, and with more detail as well.

Anyway, I saved the cognitive bias diagram on my computer desktop, and it has been sitting there since. A few days ago I opened the image and scanned around it, and saw the Image Superiority Bias. The basic idea is that we tend to remember information given to us as images more easily than information given in words. From an “amount of information” perspective, this is a bit bewildering. Compare a jpeg file to a text document: one might say an image is worth a thousand words, but the first is going to be a few MB while the other a few kB. The idiom reflects the actual way our brains work. From a biological perspective, maybe this makes sense. Interpretation of vision is an ancient process for animals, while interpretation of text or spoken word is an extremely new concept, and we still have to spend a decade or two practicing to get any good at it.

Our ability to understand and classify images quickly makes it feel like there’s a paradox in computing: my PC can easily store the text of tens of thousands of books, but until very recently computers have been pretty unreliable at pattern recognition. This is why projects like¬†Zooniverse¬†exist, in which users are asked to answer pretty simple questions about objects in a vast database of photos.

spiral_ellipse1
Computers aren’t so great at classifying galaxies, and have a tough time differentiating spiral galaxies from elliptical. Humans are real good at it. I can even tell you that the spiral arms come out clockwise from the center! (galaxyzoo.org)

Later in the day I was trying to think of a certain website that had lots of user-submitted Do It Yourself project descriptions. I couldn’t think of the name, but I DID remember that it had a funny hand-drawn robot as a mascot.

instructables-logo2x
Which is easier to remember?

“Instructables” is not a difficult name to remember. But that yellow robot sure stuck in my head more easily. I thought back on the image superiority bias I had just read about that morning.

This experience reminded me of another bias, The Baader-Meinhof phenomenon, in which it can seem like something you just learned about is suddenly popping up everywhere in your life. Sometimes the thing is actually a new song or cultural idea or whatever, and so the time you learn about it and the instances it starts showing up in your life would naturally coincide. However, this effect also happens with not-necessarily-new, but newly-learned things as well. For instance, you may have heard references to an historic figure over and over since learning about them a few weeks ago. In fact, these references might have been coming up anyway, but we have a way of filtering out a sizable chunk of the information we’re given all the time, especially that which we aren’t familiar with.

The fact that I had read about the image superiority bias just that morning, and noticed an instance of it that day, felt like a mix of observer bias and the Baader-Meinhof effect.

I tend to associate the B-M effect with the idea of Maslow’s Hammer, the idea that it’s easy “if¬†the only tool you have is a hammer, to treat everything as if it were a nail.” In both cases,¬† we preferentially deal with things in the ways I have dealt with them in the past, and ignore those ways and things we’re not familiar with. Unless we’re willing to constantly experiment with¬†everything¬†(inevitably ruining everything in the process),¬†we have to live this way to some degree.