Richard Schroeppel wrote:

It's easy to show that a cellular automaton with two states and a 4-cell neighborhood (using only the orthogonally adjacent cells, and not the diagonal cells) is relatively boring: The pattern

- 0 - 0 0 1 - 0 -

must produce a 1 in the center, or else the rule won't let patterns grow. And if this pattern produces a 1, then patterns grow in all directions at speed 1. (This does include Winograd's xor rule, which is surprising but still has quite limited behavior complexity.) Conway's great idea was to use the 8-cell neighborhood, including the diagonal neighbors. This leads to Life, and a raft of interesting goodies. My question: Suppose we stick with the 4-cell neighborhood, but break the 2-state limitation. If we allow three states, can we get interesting stuff?

We can get around the problem described above if we have the transitions - 0 - - 0 - 0 0 1 -> 2 and 0 0 2 -> 0 - 0 - - 0 - and some way for a 2 to change into a 1. I've been playing around with such rules for a few days. I haven't found any that are very Life-like, and I haven't found any good ones that have simple verbal descriptions like Life does. But there are some that are at least somewhat unpredictable. The most interesting that I've seen has a c/6 spaceship, two 2c/4 spaceships, an 8c/16 puffer producing period 6 oscillators, and a lengthening spaceship that grows at 8c/16 (producting a period 10 wick) and decays at c/7. The wickstretcher can also decay at 6c/22, leaving behind period 3 oscillators. For anyone using Mirek's Cellebration, here's a pattern showing all of those: #MCell 4.20 #GAME Neumann binary #RULE 3020220000200220000002000001220020000220220000000000000000000201 #RULE 0000000000010001001010101000101000001000000000101000001000010100 #RULE 0001000010000000000001000000000000210100010000000000010200200000 #RULE 0000000000000000002000000100000220000000200000000000 #BOARD 1500x1500 #WRAP 1 #CCOLORS 3 #L 27.A$28.A$28.A$27.A9$24.B..AA8$19.B$18.BA.A..B$19.BA.A4.AA$20.B8$8.B.B #L 11.A.B$B.B4.BA.AB4.A3.A.B4.AA$8.B.B11.A.B9$18.B8.AA$14.B3.AB.A..B$18.B #L 8$8.B.B7.B8.AA$7.BA.A.A.B3.AB.A..B$8.B.B7.B Small random patterns usually settle down to a few oscillators and some of the moving things shown above. Larger random patterns seem to grow slowly for a while, often emitting some of the things shown above. But eventually they also produce messy 2c/4 puffers, which increase the rate at which they expand, since such puffers emit perpendicular puffers, which emit others, etc., filling space with their debris. (Unfortunately, MCell on my old PC isn't fast enough to see much of that.) To describe the rule, I'll write "c/nesw -> d" to mean that if a cell is in state c and its neighbors to the north, east, south, and west are in states n, e, s, and w, respectively, then the cell will change to state d in the next generation. The rule is symmetric, so I'll only list one transition from each equivalent group. E.g. 0/0001 -> 2 also implies 0/0010 -> 2, 0/0100 -> 2, and 0/1000 -> 2. The rule is: 0/0001 -> 2 0/0011 -> 2 0/0111 -> 2 0/1111 -> 2 0/0202 -> 2 0/0222 -> 1 1/0000 -> 1 1/0002 -> 1 1/0011 -> 1 1/0101 -> 1 1/1112 -> 1 1/2222 -> 1 2/0000 -> 1 2/0002 -> 1 2/0202 -> 2 2/0212 -> 2 Except for these, all transitions have the form c/nesw -> 0. This rule convinces me that there are interesting ones of this type, but it's probably not the best of the bunch. Dean Hickerson dean@math.ucdavis.edu