simon plouffe >

I just met Jean-Paul Delahaye in Montreal and

at the conference he gave, showed to us a cellular automata that produces the primes one after the other. I will try to find a pointer to this thing, which was quite interesting to watch, it ran on a mac and I think this comes from an old program that I used to have where you could copy and paste a bitmap image and run it as if it was a cellular automaton. Except that in this case , it produces the primes. Dean Hickerson produced a Conway Life pattern in the 1980s which created a glider stream with gliders at (only) the prime numbered positions. Fun to watch. I'll pose a query of my own: 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? (Von Neumann's self-replicator construction used 29 states, and the 4-cell neighborhood.) Rich rcs@cs.arizona.edu