Cellular Automata/Formalization

From Wikibooks, open books for an open world
Jump to: navigation, search

Formalization sometimes seems an unneeded burden when learning something new, yet it is the main tool to pass scientific knowledge to others. An informal introduction into CA was already presented, now is time for a detailed formalization that will allow us to dig further into the theory of CA.


This book tries to mix rigorous mathematical formulae with self explanatory graphical representations of the same equations.

The formalization chapter is composed of the following sections:

  1. The mathematical model focuses on a general definition of one-dimensional cellular automata. At the end, it generalizes the theory to more than one dimension and functions that look more than one step into history.
  2. A neighborhood can be defined with general equations or can be described with a less general graphical definition. This chapter focuses on the last approach to describe the most common CA.
  3. A rule is a common way to define transition functions, some common ways to define a rule are described here.
  4. A pattern is used to describe a part of the content of a cellular automaton. Since some CA have been studied in detail, some patterns have been observed frequently as well. This section describes common methods for describing patterns.

Common nomenclature[edit]

A common nomenclature lookup table is provided here.


CA cellular automata

Basic symbols:[edit]

set of cell states
number of cell states in S ()
cell state (value) ()
, strings of cell values
configuration (might be finite or infinite)
finite configuration length
position index
neighborhood definition as a set of neighbors
neighborhood radius
neighborhood specific value or link in the preimage network
overlap specific value or node in the preimage network
local transition function
global transition function
time index or identifies the present

Preimage model related symbols:[edit]

preimage matrix
elements of
preimage vector
left boundary vector
right boundary vector
unrestricted boundary vector
number of preimages
link (neighborhood) weight
node (overlap) weight