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(a)cs.arizona.edu
