###### 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(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.

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