Re: Cellular Automata question
- To: mathgroup at smc.vnet.net
- Subject: [mg17535] Re: [mg17465] Cellular Automata question
- From: Robert Pratt <rpratt at math.unc.edu>
- Date: Fri, 14 May 1999 01:13:08 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Seth, If I understand correctly what you mean by an update rule (namely, a function from 25 binary variables to a single binary variable), there are 2*(2^25) = 2^26 such rules (not 2^(2^25)). Now considering rotations, we are effectively counting 2-colorings of the 5x5 grid up to rotational symmetry, and Polya theory applies. It can be shown that there are (2^25 + 2^7 + 2^13 + 2^7) / 4 = 8390720 such colorings, hence 2*(8390720) = 16781440 update rules (two choices for the image). I have also worked out the general formulas for nxn grids and m colors. The formulas differ for n even and n odd, but all are on the order of (m^(n^2)) / 4. I can post them if anyone wants. Rob Pratt Department of Mathematics The University of North Carolina at Chapel Hill CB# 3250, 331 Phillips Hall Chapel Hill, NC 27599-3250 rpratt at math.unc.edu http://www.math.unc.edu/Grads/rpratt/ On Sun, 9 May 1999, Seth Chandler wrote: > This is slightly off topic for the Mathematica group, but I am hoping > someone in this newsgroup can help? > > If one has a two dimensional cellular automaton in which site can take on > two values (0 or 1) but in which the future value depends on all sites > within a radius of 2, i.e. on 25 sites. There are 2^(2^(25)) possible update > rules. (This is a really, really big number) Suppose, however, that one can > constrain the update rules so that if m is the 5 x 5 neighborhood of a site, > the outcome of the update procedure is the same for m, and m rotated 90 > degrees, 180 degrees and 270 degrees clockwise. Now how many possible update > rules are there? > > > > >