PascGalois JE Help: Overview of 2-D Cellular Automata


Two-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 levels of elements thought of as sitting on a plane. This level is considered to be a time-step, specifically the initial time-step. Every time-step (or level) after the initial one is created by applying some update rule to the previous time-step or time-steps. This process is continued indefinitely. For example, say we use a seed level that contains just a single one.

For our update rule we will add the North, South, East and West entries of the previous level. If there is no element in one of the positions we simply use 0. The second row is now generated from the first giving.

The third row is generated from the second in the same manner,

The fourth row is generated from the third in the same manner.

In the theory this process continues indefinitely.

As with the one-dimensional automata the entries in the automaton are elements from a finite group. So if we are working in D5 using a seed of R1 and F0 the first 4 levels would look like.

As with the one-dimensional automata the entries in the automaton are then colored to help the user to see algebraic structure and patterns. The images of the first four levels that were generated above would look something like the following.

If we then stack these levels we see a three-dimensional version of this automaton.

The program is also capable of accepting seeds with more than one level and update rules that span more than just the previous level, 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

A two-dimensional finite automaton has a finite fixed width and height for each level. The update rule either wraps around or it does not. For a two-dimensional automaton there are two directions that the wrapping can be done, horizontally and vertically. Furthermore, the wrap could be done with a twist. Hence we can graph these automata on objects such as a cylinder, torus, Mobius strip or Klein bottle.

Infinite Automata

An infinite automaton is not fixed in width or height nor is it wrapped. Like in the Pascal's Triangle examples we imagine that the seed is padded indefinitely by the group identity.


Related Links: