One-dimensional cellular automata comes in two flavors, finite and infinite.
Both work in a similar manner. Both start with a seed, which is one or more
rows of elements thought of as sitting on a line. This line (or row) is considered
to be a time-step, specifically the initial time-step. Every time-step (or row)
after the
initial one is created by applying some update rule to the previous time-step
or time-steps. This process is continued indefinitely. With this terminology we
can consider Pascal's Triangle as a one-dimensional cellular automaton. Below
are the first six rows of Pascal's Triangle. Think of the first row (just the 1)
as the seed.
The second row is now generated from the first by setting each entry in the second row to the sum of the two elements directly above it. If there is no element in one of the two above positions we simply use 0. The rule where we take the sum of the two elements directly above each entry is called the update rule. The third row is generated from the second in the same manner as is the fourth from the third, and so on. In the theoretical Pascal's Triangle this process continues indefinitely.
The main feature of the PascGalois Zn program is the creation of these automata.
Since this is a computer program with limited recourses trying to work with infinite
groups can pose several difficulties. So instead of doing Pascal's Triangle on
the integers we do Pascal's Triangle on the integers modulo n. The update rule
of adding the two numbers to get the next entry is replaced by doing the addition and then
taking the result mod n. For example, if we are working in
Z5 the first 11 rows would look like.
Note: If you would like to work with other finite group structures, like Dn and Sn, please take a look at the PascGalois JE application. The layout of the PascGalois JE program is very similar to this program plus it has the ability to work with several classes of finite groups as well as products and quotients of these groups.
The program goes one step further by applying a coloring scheme to the elements
of the group to help students see algebraic structure. In the Z5
example if we continue the process for 100 rows and apply the coloring scheme we
see,
Which clearly has some nice structural properties.
The program is also capable of accepting seeds with more than one row and update rules that span more than just the previous row, or time-step. That is you can update an element by reaching back further than just the previous time-step. Furthermore, the program is capable of using a general update rule formula. You will learn more about these features on their specific pages.
Finite automata have a finite fixed width and an update that either wraps around or
does not wrap around (sometimes called null-bounded). For example, let's say
we are working in Z5 with a seed of 1 1 1 1. The update rule will
still be that of Pascal's Triangle but since we tend to stack the entries of finite
automata in columns the update rule is more like adding the element above and the one
above and one to the left. If we do not wrap the update rule we would get.
The three 2's on the second row are simply the sum of the entries above and above
to the left. The first entry of the second row is the sum of the element above it
(the 1) and the element above to the left, which does not exist and hence is taken as
0. On the other hand of we wrap the update rule we get the following.
The only difference is that the first entry of the second row is now a 2. This
entry is gotten from the element directly above and above left. Now the above left
element is wrapped around to the last element of the first row (another 1). You
can think of wrapped update rules as being drawn on a cylinder. On a cylinder moving
to the left (or right) automatically wraps around the cylinder. For example,
let's stick with Z5 and take the random seed of,
The first 50 rows of this finite automata (with wrapping) looks like,
On closer inspection you will see that this image eventually repeats every 20 rows, hence the period of this automaton is 20.
An infinite automaton is not fixed in width nor is it wrapped. Like in the
Pascal's Triangle examples we imagine that the seed is padded indefinitely on both
sides by the group identity. So for Pascal's Triangle the seed row of 1 is really
... 0 0 0 1 0 0 0 ..., hence the term infinite. So the examples at the beginning
of this page are all infinite automata. For example, if we are working in
Z5 with seed 1 and Pascal's update rule the first 11 rows would look like.
and applying the coloring scheme to the first 100 rows looks like,