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