If I haven't been posting much here in the last couple of weeks, it's because too much of my writing energy has been going into writing actual papers. Here's one of them: Growth and Decay in Life-Like Cellular Automata, arXiv:0911.2890. The aim of the paper is to predict which two-dimensional cellular automaton rules will behave similarly to Conway's Game of Life. But a large part of the difficulty in making this sort of prediction is finding the right definition of "similarly".

( Read more... )

Life without Death is a cellular automaton with the same rule for creating new live cells as Conway's Game of Life, but in which no live cell ever dies. Despite the inability to create oscillators or spaceships (both of which require some cells to die sometimes) it has interesting dynamics due to the existence of ladders, patterns that grow at speed c/3 (that is, one unit of growth for every three time steps of the cellular automaton). Typical random seeds end up with from one to four chaotic regions spreading diagonally from the starting region, spewing ladders on both sides of them so that one ends up with a pattern in which the four quarters of the pattern (as split on roughly diagonal lines) are striped by axis-parallel ladders, separated by the chaotic regions. The chaotic regions separating the striped quarters tend to grow wider, but slowly as the pattern grows, and the boundary of the chaotic regions keeps pace with the ladders (probably in a self-limiting way: there is a pattern that grows at speed 2c/3 along the side of a ladder and then erupts in chaos at the tip, so if the chaotic growth regions ever fell too far behind they would catch up using this mechanism).

Patterns of this type can be simulated to hundreds of thousands of time steps using the Hashlife algorithm embedded into Golly.

But as it turns out there is another ladder, one that can grow more quickly (the text below is a pattern format that can be copied and pasted into Golly):

x = 26, y = 15, rule = B3/S012345678
obobobobobobobobobobo$23o$3ob3ob3ob3ob3ob3o$26o$26o$ob3ob3ob3ob3ob3ob
3o$3ob3ob3ob3ob3ob3obo$25o$3ob3ob3ob3ob3ob3obo$ob3ob3ob3ob3ob3ob3o$26o
$26o$3ob3ob3ob3ob3ob3o$23o$obobobobobobobobobobo!

Rather than growing at speed c/3, it grows at speed 4c/9. I've only seen this once out of many chaotic starting seeds, but if it happens once it should happen more than once. My suspicion is that most chaotic patterns should have a shape that eventually comes to be dominated by these faster ladders, but that even hundreds of thousands of steps isn't enough to see this domination.

ETA: animated gif by Simpsons contributor, who set this all off by starting a Wikipedia article on LwoD.

ETA2, 6/13: Already discovered in October 2000 by Dean Hickerson, who also found ladders of speeds 4c/10 and 4c/13. Dean's patterns: ( Read more... )

Gabriel Nivasch describes a simple model for generating random or pseudorandom walks. Although it can be simulated directly with a cellular automaton (and came up in trying to understand the behavior of certain spaceship-replicator interactions in the 2d cellular automaton rule B25/S4), much faster algorithms for simulating it are possible.

There's been some interesting discussion over on the computational complexity blog about Wolfram's problem of determining whether a particular Turing machine with 2 states and 3 symbols is universal, a problem he's offering $25,000 to solve. The CC blog discussion has largely been on what makes a problem like this one interesting or not interesting. My own response is that I'm not terribly excited by the problem of finding minimum Turing machines, because I think the Turing machine model itself is a bit inelegant, but that the search for a proof for this problem could still lead to some interesting techniques. I do have some additional connection to the problem, though, which I think may still be of some interest at this late date.

( Read more... ) ETA 24 Oct '07: Wolfram's problem has been solved! And, as Gabriel Nivasch informs me, I was mistaken that Cook had never ended up publishing his proof: it's in Complex Systems v.15.

Golly is a cross-platform cellular automaton simulator that incorporates hashlife algorithms, allowing it to simulate most Game of Life patterns for astronomical numbers of generations quickly. Version 1.0 was just released, and now also incorporates Python scripting, allowing the construction of astronomically complex patterns via modular high level programming rather than bit-at-a-time copy and pasting.

For instance, here is bricklayer.py, a pattern first found by David Bell in 2002 that is formed by combining two p22 oscillators to make a gun, combining three p22 guns to make a p154 gun, and combining two p154 guns with a p7 glider reflector and a messy small Life pattern called "lumps of muck". By itself, lumps of muck forms two subpatterns that, individually, would themselves turn back into LoM again, but unfortunately interfere with each other creating a mess. The streams of gliders from the two guns and reflector repeatedly hit the back subpattern, creating a block and allowing the other subpattern to grow without interference, effectively pushing the LoM forward diagonally at each step. It ends up forming two long diagonal sequences of blocks, with the guns at one end of the sequence, the LoM on the other, and the gliders running down the middle.

( Python )

And here it is in the previously standard form for such patterns, a run-length-encoded text file:

( RLE )

If you want to see the pattern itself within Golly, either one works equally well, but I think you can see which one is more human readable and modifiable as source code.

This is making me think the push-pull replicator-based spaceships that should exist in HighLife and B368/S12578 may be within reach of construction now...

Via Pharyngula: Good Math, Bad Math. "Shredding bad math and squashing the crackpots who espouse it." Seems to be focusing mainly on mathematically-challenged creationists for now, though he does have a recent post on modeling physics by cellular automata.

A Neighborhood of Infinity finds the power series expansion of tan(x) (somehow related to Joyce trees and Tremolo permutations) using a cute cellular-automaton-like iteration.

( Python implementation )

ETA: ANoI's explanation

I just reloaded Fano, after updating it to OS X 10.4.5. New content includes citations from Graph Drawing 2005 and SODA 2006, and new spaceships from Evan Clark in several CA rules including Amoeba, Day & Night, Holstein, and Stains.

I just ran across a new journal, The International Journal of Unconventional Computing, with four issues published so far. As is not so unusual these days, its papers are available free online. Unfortunately, like too many online paper repositories, it appears to have no RSS feed.

Of most interest to me: Glider Dynamics in 3-Value Hexagonal Cellular Automata: The Beehive Rule which describes some simple CA rules with complex behavior. I must admit, though, that I'm a little put out at their statement that, among known binary CA rules, Life "appears to be somewhat unique" in its glider dynamics, since my CA glider database shows that Life is very far from being "somewhat unique" in this respect.

The special issue on artificial immune systems may also have some interest to security researchers, or it may just be blue sky, it's hard for me to tell.

Hans Thomsen shows off some drawings of synthetic small world graphs. Showing an interesting if unsurprising progression from order to chaos as the beta parameter increases.

He also has an earlier post about cellular automata. Looks like a blog for me to watch more regularly...

Just updated the web server on Fano. Some minor additions to the bibliographic data there, but nothing very thorough — I haven't been very well motivated to work on that now that Google scholar has become so much more complete and reliable than Citeseer ever was.

The more interesting addition to the server, to me, is The Seal, a new c/6 diagonal spaceship in Life, discovered by Nicolay Beluchenko. It's not easy to add new entries to the list of known Life spaceship velocities; the most recent one prior to this was the much larger and more complicated 17c/45 Caterpillar last December.

New cross-platform cellular automata application by Tomas Rokicki and Andrew Trevorrow. It's still in alpha stages, lots of bugs and missing features, but looks very promising: a combination of the ease of use of Trevorrow's LifeLab with the simulation power of Rokicki's hashlife.

And while I'm posting pointers to Game of Life stuff, H. Koenig's Game of Life News blog is a great new resource.