GS 2003/Math - Collins
Lab 12
Cellular Automata: Cases for 1D

Cellular Automata: One Dimension, Easiest Cases

We are going to work together to classify all 256 CAs
for the case when the dimension is 1, the neighborhood
size has radius 1, and there are only two colors: black and white.

Under these conditions there are only 8 possible input states
for p=value to left, q=value at cell, r = value to right

   p q r   state #
   -----   -------
   0 0 0      0
   0 0 1      1
   0 1 0      2
   0 1 1      3
   1 0 0      4
   1 0 1      5
   1 1 0      6
   1 1 1      7

The 256 CAs are numbered from 0-255, with the binary form
of the number representing the output values for the 8
possible input states.  For example for CA#30, we have
30 = 2 + 4 + 8 + 16 = 01111000 in base 2, and these
are the outputs for states 0-7 in reverse order.

Using the Programs

Rather than have you develop a program, I've written programs
and attached them at the end of this file.  Before you
go further, go ahead an copy them into M-files and save
them.

There are two MATLAB functions catable.m and caapply.m

catable This function takes a rule as input, prints out the
          input/output table for the rule.  You can input the rule
          as a number 0-255, like catable(33) or as a rule involving p,q,r.  For example
          you could have the rule that sets the value to 1 if r is 1
          and 0 if r is 0 (moves all to the left); the rule for this is
          'r', and you just would type catable('r')

          This function will also return the 8 output values (if asked).
          Try z = catable(33)

caapply This function takes a rule and other optional inputs,
          applies the rule over and over, and displays the final result.
          The easiest way to use this function, is to to type
              caapply(33)
          The default values are to do 100 iterations, using an array of
          128 values, with an initial value of random list of 1s and 0s.

          If you want to use a different initial value type
              x0 = zeros(1,128);   % start with all zeros
              x0(5) = 1; x0(64) = 1; x0(100) = 1;   % set certain values to 1
              caapply(33,x0)
          You can also specify the initial value as a single number that
          will be converted to binary and used as the starting value.

          If you want to change the number of iterations to 200 and
          the array size to 256, use
              caapply(33,x0,200,256)
          Note: in this case the initial value x0 must have 256 
          elements (or whatever length you set)

Assignment

   1. Copy the two programs below and save them (use the given names).
      Test that it works by typing caapply(33)
      The result should look something like this:

Yours may look different because it is based on a random initial guess. 2. Each of you has a range of 16 numbers representing 16 different rules to test. For each rule you should run it at least twice, once with a random initial value (the default) and once with a single 1 in the middle of a row of all zeros (you can use the method as described above to make your initial guess, or you can just use the value 2^64) 3. For each rule you need to classify the results into one of the 4 following classes: Class 1 - Tends towards a fixed value (like all white) Class 2 - Cycles between values Class 3 - No discernible pattern (chaos) Class 4 - Different initial guesses have distinctly different behavior; many, but not all, tend towards all white/black It may be hard to differentiate between 3 and 4. Just do your best. Make sure you hand in your results before you leave today. 4. Your number range: Sam 0- 15 Austin 80- 95 Stuart 160-175 Charlie F. 16- 31 Chris 96-111 Michael 176-191 Meara 32- 47 Scott 112-127 Michelle 192-207 Jennifer 48- 63 Steve 128-143 Angela 208-223 Charlie W. 64- 79 Matthew 144-159 Lena 224-239 5. (When Done) Work on your project! 6. (Challenge) Develop a program for a cellular automatum with a neighborhood of radius > 1, or using more that 2 colors. If you choose to pursue this, let me know and I can give you some hints. -----------------------PROGRAMS---------------------------- caapply.m function caapply(rule,x0,N,M) % applies the CA rule 'rule' for N iterations % with input of length M, and initial value x0 % (x0 can be an array of length M or a value) outp = catable(rule); if (nargin<4) if ((nargin>1) & (length(x0)>1)) M = length(x0); else M = 128; end if (nargin<3) N = 100; if (nargin<2) x0 = (rand(1,M)<0.5); end end end res = zeros(N,M); if (length(x0)==1) b = x0; j = M; while(j>0) x0(j) = mod(b,2); b = floor(b/2); j = j - 1; end end res(1,:) = x0; ind1 = [M,1:M-1]; ind2 = [2:M,1]; for i = 1:N-1 p = res(i,ind1); q = res(i,:); r = res(i,ind2); v = p*4+q*2+r; res(i+1,:) = outp(v+1); end image(res+1) bw = [1 1 1;0 0 0]; colormap(bw) catable.m function outp = catable(rule) % given a rule (expression of p, q, r or a number) % writes out the input/output table ct = 1; for p = 0:1 for q = 0:1 for r = 0:1 if (isstr(rule)) out = eval(rule); else out = mod(rule,2); rule = floor(rule/2); end disp([p q r out]) x(ct) = out; ct = ct + 1; end end end if (nargout==1), outp = x; end
Mail: ccollins@math.utk.edu