PascGalois JE Help: Overview of 1-D Cellular Automata


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 JE 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 finite group structures. The update rule of adding the two numbers to get the next entry is replaced by doing the group operation on the two above group elements. For example, if we are working in Z5 the first 11 rows would look like.

If we are working in D5 using a seed of R1 and F0 the first 7 rows would look like.

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

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.

Infinite Automata

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,




Related Links: