Cellular Automata/Formalization

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 nomenclatureEdit

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